Design hash table


  • 0
    N

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

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

  • 0

    @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)


  • 0
    N

    @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.


  • 0

    @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 add() current phase no should also be added
    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.


  • 0
    R

    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;
    	private double loadThreshold;
    
    	@SuppressWarnings("unchecked")
    	public HashMap(int capacity, double loadTreshold) {
    		this.capacity = capacity;
    		this.loadThreshold = loadTreshold;
    		this.size = 0;
    		this.bucket = new Entry[capacity];
    
    	}
    
    	@SuppressWarnings("unchecked")
    	public HashMap() {
    		this.capacity = 1;
    		this.loadThreshold = 0.75;
    		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 {
    			Entry<K, V> head = bucket[index];
    			while (head != null && !head.key.equals(key))
    				head = head.next;
    
    			if (head == null) {
    				bucket[index] = new Entry<K, V>(key, value);
    				bucket[index].next = head;
    				size++;
    			} else
    				head.value = value;
    		}
    
    		double currLoad = (double) size / capacity;
    		if (currLoad > loadThreshold)
    			reHash();
    	}
    
    	public boolean lookup(K key) {
    		int index = getHashedIndex(key);
    
    		if (bucket[index] == null)
    			return false;
    
    		Entry<K, V> head = bucket[index];
    		while (head != null && !head.key.equals(key))
    			head = head.next;
    
    		if (head == null)
    			return false;
    		return true;
    	}
    
    	public V get(K key) {
    		if (!lookup(key))
    			return null;
    		int index = getHashedIndex(key);
    		Entry<K, V> head = bucket[index];
    		while (head != null && !head.key.equals(key))
    			head = head.next;
    		return head.value;
    	}
    
    	public boolean delete(K key) {
    		if (!lookup(key))
    			return false;
    		int index = getHashedIndex(key);
    		Entry<K, V> head = bucket[index];
    		if (head.key.equals(key)) {
    			bucket[index] = head.next;
    		} else {
    			Entry<K, V> prev = head;
    			head = head.next;
    			while (head.next != null && !head.key.equals(key)) {
    				prev = head;
    				head = head.next;
    			}
    			prev.next = head.next;
    		}
    		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)
    				add(e.key, e.value);
    		}
    	}
    
    	private int getHashedIndex(K key) {
    		return Math.abs(key.hashCode()) % capacity;
    	}
    
    	public static void main(String[] args) {
    		HashMap<Integer, String> map = new HashMap<>();
    		map.add(1, "Hello");
    		map.add(2, "pure");
    		map.add(3, "storage");
    		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));
    
    	}
    }
    

  • 2
    K

    @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){
    				add(e.key, e.value);
                                    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 {
    			Entry<K, V> head = bucket[index];
    			Entry<K, V> curr = head;
    			while (curr != null && !curr.key.equals(key))
    				curr = curr.next;
    
    			if (curr == null) {
    				bucket[index] = new Entry<K, V>(key, value);
    				bucket[index].next = head;
    				size++;
    			} else
    				curr.value = value;
    		}
    
    		double currLoad = (double) size / capacity;
    		if (currLoad > loadThreshold)
    			reHash();
    	}
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.