Как работает итератор хэш-таблицы?

673
30 января 2017, 17:14

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

Как мне сделать такой итератор в данном контексте? Буду безумно благодарен за любую помощь, советом или кодом...

Вот код самого справочника:

public class ReferenceBook<K, V> implements Book<K, V> {
    private Node<K, V>[] hashTable;
    private final float DEFAULT_LOAD_FACTOR = 0.75f;
    private float threshold = hashTable.length * DEFAULT_LOAD_FACTOR;
    private int size = 0;
    ReferenceBook() {
        hashTable = new Node[16];
    }
    @Override
    public boolean insert(K key, V value) {
        return false;
    }
    @Override
    public boolean delete(K key) {
        return false;
    }
    @Override
    public V get(K key) {
        return null;
    }
    @Override
    public Iterator<V> iterator() {
        return new Iterator<V>() {
            int countArray = 0;
            // Вот тут корень моих проблем. Подскажите что я могу предпринять чтобы итератор работал как надо?
            @Override
            public boolean hasNext() {
                return currentCellOfTableHaveMoreElement() || arrayTableHaveMoreCell();
            }
            private boolean arrayTableHaveMoreCell() {
                return countArray < hashTable.length;
            }
            private boolean currentCellOfTableHaveMoreElement() {
                return hashTable[countArray].getNext().getValue() != null;
            }
            @Override
            public V next() {
                return null;
            }
        };
    }

    private class Node<K, V> {
        private Node<K, V> next;
        private int hash;
        private K key;
        private V value;
        Node(K key, V value, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
            initHash();
        }
        private void initHash() {
            hash = 31;
            hash = hash * 17 + key.hashCode();
            hash = hash * 17 + next.hashCode();
            hash = hash * 17 + value.hashCode();
        }
        public Node<K, V> getNext() {
            return next;
        }
        public K getKey() {
            return key;
        }
        public V getValue() {
            return value;
        }
        @Override
        public int hashCode() {
            return hash;
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj instanceof Node<?, ?>) {
                Node<K, V> node = (Node) obj;
                return (Objects.equals(key, node.getKey()) &&
                        Objects.equals(value, node.getValue()) ||
                        Objects.equals(hash, node.hashCode()));
            }
            return false;
        }
    }
}
Answer 1

Самую примитивную реализацию прохода по всем элементам HashMap можно сделать примерно так:

for (int i=0; i<hashTable.length; i++) {
    if (hashTable[i] != null) {
        Node<K, V> node = hashTable[i];
        do {
            System.out.println(node.getValue());
            node = node.getNext();
        } while (node != null);
    }
}

Но данный подход неоптимален, так как просматриваются все элементы массива. Его можно усовершенствовать, используя значение size:

int count = 0;
for (int i=0; count != size; i++) {
    if (hashTable[i] != null) {
        MyNode<K, V> node = hashTable[i];
        do {
            System.out.println(node.getValue());
            count++;
            node = node.getNext();
        } while (node != null);
    }
}

В этом варианте HashMap просматривается до тех пор, пока в нем есть элементы.

А итератор можно примерно так реализовать:

public Iterator<V> iterator() {
    return new Iterator<V>() {
        int currentNodeNumber = 0;
        int currentArrayIndex = 0;
        Node<K, V> currentNode;
        @Override
        public boolean hasNext() {
            return currentNodeNumber < size;
        }
        @Override
        public V next() {
            for (; currentNodeNumber != size; currentArrayIndex++) {
                if (hashTable[currentArrayIndex] != null) {
                    if (currentNode == null) {
                        currentNode = hashTable[currentArrayIndex];
                    }
                    currentNodeNumber++;
                    V value = currentNode.getValue();
                    currentNode = currentNode.getNext();
                    if (currentNode == null) {
                        currentArrayIndex++;
                    }
                    return value;
                }
            }
            return null;
        }
    };
}
READ ALSO
Android, вопрос про mipmap

Android, вопрос про mipmap

Добрый день, возник вопрос: стоит ли каждые изображения закидывать в mipmap?

462
Логика работы метода push в хеш таблице

Логика работы метода push в хеш таблице

Здравствуйте, я нашел вариант реализации хэш-таблицы, но мне непонятна логика работы метода push:

316
Ошибка при загрузке с сервера файла.Socket. Android. Java. :Connection reset by peer: socket write error.

Ошибка при загрузке с сервера файла.Socket. Android. Java. :Connection reset by peer: socket write error.

Реализую передачу между устройствами при помощи socket'овПередача проходит между Windows ПК и Android девайсом

487
Когда можно использовать imageView.setImageBitmap(bitmap). Чем еще кроме канвас динамично менять изображение в ImageView

Когда можно использовать imageView.setImageBitmap(bitmap). Чем еще кроме канвас динамично менять изображение в ImageView

вот есть у меня imageview , если в методе onCreate я присваиваю imageViewsetImageBitmap(bitmap), то всё нормально отображается

498