Design a Hash Table

Java

//需要创建一个Cell类用来追踪original key  
//1. 实现hash function  
//2. 实现put(key, value)  
//3. 实现get(key)  
public class Hash<K, V>{  
    LinkedList<Cell<K, V>>[] items;  

    public Hash(){  
        items = new LinkedList<Cell<K, V>>[10];  
    }      

    //实现hash function  
    public int hashFunction(K key){  
        return key.toString().length() % items.length;  
    }  

    //实现put方法  
    public void put(K key, V value){  
        int hashedKey = hashFunction(key);  

        //如果没有这个key就新建一个linked list  
        if(items[hashedKey]==null){  
            items[hashedKey] = new LinkedList<Cell<K, V>>();  
        }  

        LinkedList<Cell<K, V>> collided = items[hashedKey];  

        for(Cell<K, V> c : collided){  
            if(c.equivalent(key)){  
                collided.remove(c);  
                break;  
            }  
        }  

        Cell<K, V> cell = new Cell<K, V>(key, value);  
        collided.add(cell);  
    }  

    //实现get方法   
    public V get(K key){  
        int hashedKey = hashFunction(key);  

        if(items[hashedKey]==null){  
            return null;  
        }  

        LinkedList<Cell<K, V>> collided = items[hashedKey];  

        for(Cell<K, V> c: collided){  
            if(c.equivalent(key)){  
                return c.getValue();  
            }  
        }  
        return null;  
    }  
}  

//我们需要一个Cell类来追踪original key  
public class Cell<K, V>{  
    K key;  
    V value;  

    public Cell(K k, V v){  
        key = k;  
        value = v;  
    }  

    public K getKey(){  
        return key;      
    }  

    public V getValue(){  
        return value;  
    }  

    public boolean equivalent(K key){  
        if(this.getKey() == key){  
            return true;  
        }  
        return false;  
    }  
}