Hello, dear colleagues, I have a task to create a reference book on the HashMap image, and when I started doing methods for adding, inserting, and the like, I ran into a problem: I need an iterator that will first look at the cell, then go through the linked list in it and move on to the next one, and I don't understand how I can do it. It is clear that this should be something like an iterator iterator, and I even did such a task, but those were iterators on arrays, and here I have an external array level, and internal linked lists, and I'm at a dead end.

How do I make such an iterator in this context? I would be very grateful for any help, advice or code ...

Here is the code for the directory itself:

 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; } } }
  • Why do you need an iterator iterator? What restrictions are imposed on the iterator? - Mikhail Vaysman
  • Not at all on the topic, but you have some kind of trouble with the Node hashcode. There will be NPE when referring to next (because you somehow need to create the first Node), and value has the right to change. And should the Node hashcode ever change when next appears or the value changes? - etki
  • @etki yes there are problems there, I just have not reached it. - Pavel
  • @Mikhail Vaysman about iterator iterators is just an assumption, the main thing is to figure out how to go through the hash table according to the principle: we take the first cell through the entire list and then the second through the entire list and so on ... - Pavel

1 answer 1

The most primitive implementation of passing through all elements of a HashMap can be done like this:

 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); } }

But this approach is not optimal, since all elements of the array are viewed. It can be improved using the size value:

 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); } }

In this embodiment, the HashMap viewed as long as there are items in it.

And the iterator can be implemented like this:

 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; } }; }
  • Hello again)), thanks for your answer, but I have 2 questions: 1. in the hash table, the index when added is calculated from int index = hash (key)% hashTable.length how can we go to the table just by iterating array will be a hole null then we will not know what will happen next. 2. and if at us the conflict is solved through adding in the same cell, to the linked list? The elements that are second in the cell, we will not see? Or am I misunderstanding something? I mean the first 2 pieces of code. - Pavel
  • @Pavel, 1. If there is a null in a basket, it means that there is nothing in this basket, therefore, you can move on to the next basket. 2. Yes, the case of collisions is solved this way. We will see. I wrote this code not on my knee, but checked it. Try to go through the debugger on the code, perhaps the algorithm of work will become clearer. - post_zeew
  • >>> I did not write this code on my knee, but I checked <<< I didn’t even think about hinting at it, I just asked ... - Pavel