# Design hash table

• Design a data structure `Map<Integer, Integer>` supporting the following operations and requirements:

2. delete: O(1)
3. lookup: O(1)
4. clear:O(1)
5. iterate: O(number of elements)

• @nixed Can you confirm that clear is O(1)? As far as I know "clear " remove all map entries. If this is like that could they be removed with time complexity O(1)

• @elmirap Yes, clear must be O(1). You can set the size to 0 for clear operation. It's okay to sacrifice space for extra speed.

Hint: You will need two arrays.

• @nixed One more array can be used to store the phase no of each element.
cur_phase_no=0
Every time clear() is called the current phase number is incremented.
In lookup() we have to check:
if element phase number is equal to current phase no. then return that element
else return 0
Delete() can be done by setting element to 0.
Iterate(): to iterate all elements we can maintain list.

• Here is my implementation using sequence chaining.
The amortized time for get, add, lookup, clear, delete is O(1). and iterate is O(n).
Please let me know if you find anything wrong.

``````class Entry<K, V> {
K key;
V value;
Entry<K, V> next;

Entry(K key, V value) {
this.key = key;
this.value = value;
next = null;
}

@Override
public String toString() {
return key.toString() + ":" + value.toString();
}
}

public class HashMap<K, V> {
private Entry<K, V> bucket[];
private int capacity, size;

@SuppressWarnings("unchecked")
public HashMap(int capacity, double loadTreshold) {
this.capacity = capacity;
this.size = 0;
this.bucket = new Entry[capacity];

}

@SuppressWarnings("unchecked")
public HashMap() {
this.capacity = 1;
this.size = 0;
this.bucket = new Entry[capacity];
}

public void add(K key, V value) {
int index = getHashedIndex(key);
if (bucket[index] == null) {
bucket[index] = new Entry<K, V>(key, value);
size++;
} else {

bucket[index] = new Entry<K, V>(key, value);
size++;
} else
}

double currLoad = (double) size / capacity;
reHash();
}

public boolean lookup(K key) {
int index = getHashedIndex(key);

if (bucket[index] == null)
return false;

return false;
return true;
}

public V get(K key) {
if (!lookup(key))
return null;
int index = getHashedIndex(key);
}

public boolean delete(K key) {
if (!lookup(key))
return false;
int index = getHashedIndex(key);
} else {
}
}
size--;
return true;
}

@SuppressWarnings("unchecked")
public void clear() {
bucket = new Entry[capacity];
this.size = 0;
}

public int size() {
return size;
}

public Iterator<Entry<K, V>> getIterator() {
Iterator<Entry<K, V>> it = new Iterator<Entry<K, V>>() {
int count = 0;
int index = 0;
Entry<K, V> curr = bucket[index];

@Override
public boolean hasNext() {
return count < size;
}

@Override
public Entry<K, V> next() {
if (count >= size)
return null;

while (index < capacity && curr == null) {
index++;
curr = bucket[index];
}
Entry<K, V> temp = curr;
count++;
curr = curr.next;
return temp;
}
};
return it;
}

@SuppressWarnings("unchecked")
private void reHash() {
capacity += capacity * 2;
Entry<K, V> temp[] = bucket;
bucket = new Entry[capacity];
size = 0;
for (Entry<K, V> e : temp) {
if (e != null)
}
}

private int getHashedIndex(K key) {
return Math.abs(key.hashCode()) % capacity;
}

public static void main(String[] args) {
HashMap<Integer, String> map = new HashMap<>();
System.out.println(map.lookup(2));
Iterator<Entry<Integer, String>> it = map.getIterator();
while (it.hasNext()) {
System.out.println(it.next());
}
System.out.println(map.lookup(2));
System.out.println(map.lookup(5));
System.out.println(map.delete(2));
System.out.println(map.lookup(2));
map.clear();
System.out.println(map.lookup(1));

}
}
``````

• @root I think your reHash function is missing to add more than 1 elements at the same index. Below is the correct version.

``````	@SuppressWarnings("unchecked")
private void reHash() {
capacity = capacity * 2;
Entry<K, V> temp[] = bucket;
bucket = new Entry[capacity];
size = 0;
for (Entry<K, V> e : temp) {
while (e != null){
e = e.next;
}
}
}
``````

Also when you add to the same array index, previous entries were gone. Corrected as below:

``````	public void add(K key, V value) {
int index = getHashedIndex(key);
if (bucket[index] == null) {
bucket[index] = new Entry<K, V>(key, value);
size++;
} else {
while (curr != null && !curr.key.equals(key))
curr = curr.next;

if (curr == null) {
bucket[index] = new Entry<K, V>(key, value);