0

Дали задание написать простой HashMap c тестами

public class SimpleHashMap<K,V> implements Iterable
параметризован T почему то не показывает

 private T[] array;
    private int load;
    private int modCount;
    private int size;

public SimpleHashMap() {
    this.array = new T[16];
    load = (int) (array.length * 0.75);
}

public boolean insert(K key, V value) {
    boolean result = false;
    int index = -1;
    T temp = new T(key, value);
    index = hash(key);
    if (size + 1 &gt;= load) {
        load *= 2;
        expensive();
    }
    if (array[index] == null) {
        array[index] = temp;
        result = true;
        size++;
        modCount++;
    }
    return result;
}

public int getSize() {
    return size;
}

private void expensive() {
  T[] temp = array;
  array = new T[temp.length * 2];
  size = 0;
  for (T tmp : temp) {
      if (tmp != null) {
          insert((K)tmp.getKey(), (V)tmp.getValue());
      }
  }
}

public V get(K key) {
    return (V) array[hash(key)].getValue();
}

public boolean delete(K key) {
   boolean result = false;
   if (array[hash(key)] != null) {
       array[hash(key)] = null;
       size--;
       modCount++;
       result = true;
   }
   return result;
}

public int hash(K key) {
   int temp = 31;
    temp = temp * 17 + key.hashCode();
    return temp % array.length;
}


@Override
public Iterator&lt;T&gt; iterator() {
    return new Iterator&lt;T&gt;() {
        private  int expectedModCount = modCount;
        private int position = 0;
        @Override
        public boolean hasNext() {
            return position &lt; size;
        }

        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            } else if (expectedModCount != modCount) {
                throw new ConcurrentModificationException();
            }
            return array[position++];
        }
    };
}




и тест


@Test
        public void whenCreateIteratorThen() {
        SimpleHashMap<Integer, String> map = new SimpleHashMap<>();
        map.insert(12, "one");
        map.insert(1, "two");
        Iterator<T> it = map.iterator();
        assertThat(it.hasNext(), is(true));
        assertThat(it.next().getKey(), is(1));
        assertThat(it.hasNext(), is(true));
        System.out.println(it.hasNext());
        assertThat(it.next().getKey(), is(12));
        assertThat(it.hasNext(), is(false));
    }

не пойму почему не работает итератор кидает NullPointerexception

. почему то не хочет показывать

Terasan
  • 159

2 Answers2

1

Не знаю тот ли это ответ который ожидается, но попробую.
Нельзя "напрямую" создавать массив дженериков, соответственно строка:
this.array = new T[16]; абсолютно некорректна, её можно заменить на что-то вроде:
this.array = (T[]) Array.newInstance(clazz, 16);, где clazz - класс, для типа T, переданный в конструктор или ещё как-то. Вот тут подробнее.

public class SimpleHashMap<K,V> implements Iterable параметризован T

Если я правильно понял, то это значит:

public class SimpleHashMap<K,V> implements Iterable<T> {

Так тоже делать нельзя, т.к. Т нигде предварительно заявлен не был. Если особо в код не лезть, то можно сделать так (я понимаю, что это не соответствует заданию, зато очень наглядно):

public class SimpleHashMap<K,V,T> implements Iterable<T> {

Я бы посоветовал хранить значения не в массиве, а в списке. Что-то вида List<Pair<K,V>>, где Pair внутренний класс, который содежрит ключ-значение. Можно даже не список, а set. Не придётся самому думать про его размер. Если это не вариант, тогда хранить эти пары в массиве Pair<K,V>, или два массива: один под ключ, другой под значение.
Также не не корректна эта строка:

insert((K)tmp.getKey(), (V)tmp.getValue());

Откуда берутся эти два метода? Компилятор про них ничего не знает. Чтобы он про них что-то знал, можно сделать что-то вида (что также не соответствует заданию):

public class SimpleHashMap<K extends Getable, V extends Getable,T> implements Iterable<T> {

где Getable интерфейс с поддержкой метода get().

afjord
  • 406
1

Должна вам сказать, в мапе не используется Iterable - в ней принципиально другой способ хранения данных. введите сюда описание изображения

Вы можете убедиться в этом, заглянув в исходники. Для того, чтобы определить, куда запихнуть пару, у ключа не вычисляется заново хеш - он берется сразу методом hashCode(), поэтому хешмапа такая и быстрая. Она представляет из себя ассоциативный массив, вовсе не список.

При вычислении хешкода объекта случаются коллизии, когда хешкод совпадает, и тогда значения помещаются на тот же индекс в односвязный список - пока не достигнут какого-то максимума, например, в 8 элементов. После преодоления этой цифры список превращается в черно-белое дерево, чтобы поиск происходил быстрее.

Тоесть: вы просите мапу выдать вам значение по ключу - она смотрит и видит, что у нее там несколько значений, она берет ваш ключ и ходит по односвязному списку и сравнивает каждое значение, поэтому для хранения каких-то объектов в них обязательно должны быть переопределены методы equals() и hashCode()

Черное-белое дерево же нужно для того, чтобы, когда список станет слишком большим, поиск можно было осуществить с помощью алгоритма типа "разделяй и властвуй". Но, как правило, такого не происходит, если хеш-коды у объектов определены хорошо.

Но кстати, насчет того на какой индекс запихивать элемент - зависит от реализации. Так же, HashSet в java использует под капотом мапу, только значения у нее null

Исходя из все вышесказанного, я бы на вашем месте переписала половину, наверняка, ваше решение будет rejected

Можете добавить node и уже из него пилить массив:

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

    Node(int hash, K key, V value, Node&lt;K,V&gt; next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + &quot;=&quot; + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry&lt;?,?&gt; e = (Map.Entry&lt;?,?&gt;)o;
            if (Objects.equals(key, e.getKey()) &amp;&amp;
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}




========================


Node<K,V>[] table;


(p.s. from HashMap docs)

А насчет итератора - его можно будет поотдельности добавить в ValueSet/KeySet

Elizaveta
  • 408