HashMap

1，链表法。

public class HashMap<K,V> {
    public static class Node<K,V> {
        K key;
        V value;
        Node next;
        public Node(K key, V value, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    
    private Node<K,V> tab = new Node<K,V>[16];
    private ReentrantLock[] locks = new ReentrantLock[16];
    
    public void put(K key, V value) {
        if(key == null || value == null) {
            throw new NullPointerException("illegal arguments");
        }
        int index = indexOf(key);
        final locker = locks[index];
        locker.lock();
        try{
            Node<K, V> node = tab[index];
            if(node == null) {
                tab[index] = new Node<K,V>(key, value, null);
            } else {
                while(node != null && node.key != key && !node.key.equals(key)) {
                    node = node.next;
                }
                if(node == null) {
                    tab[index] = new Node<K,V>(key, value, tab[index]);
                } else {
                    node.value = value;
                }
            }
        } finally {
            locker.unlock();
        }
    }
    
    public V get(K key) {
        if(key == null) {
            throw new NullPointerException("illegal arguments");
        }
        int index = indexOf(key);
        final locker = locks[index];
        locker.lock();
        try{
            Node<K, V> node = tab[index];
            while(node != null) {
                if(node.key == key || node.key.equals(key)) {
                    return node.value;
                } else {
                    node = node.next;
                }
            }
            return null;
        } finally {
            locker.unlock();
        }
    }
    
    private int indexOf(K key) {
        if(key == null) return 0;
        int hash = key.hashCode();
       // return hash%tab.length;
       return hash&(tab.length-1); // length of tab is 2^n;
    }
}

 

2，线性探测法。

public class HashTable {
    Item[] hashArray;
    int arraySize;//定义数组长度
    public HashTable(int size){//构造器，初始化
        arraySize = size;
        hashArray = new Item[arraySize];
    }
    //哈希函数
    public int hash(int key){
        return key % arraySize;
    }
    //插入，这里假设是数组未满，即不能插入大于arraySize的数据数
    public void insert(Item item){
        int key = item.getKey();
        int hashCode = hash(key);
        //若已存在同样的数据，则向下进一位，直到找到空的位置
        //为了简单，也可要求不准有重复数据
        while(hashArray[hashCode] != null){
            ++hashCode;
            hashCode %= arraySize;
        }
        hashArray[hashCode] = item;
    }
    //删除
    public Item delete(int key){
        int hashCode = hash(key);
        while(hashArray[hashCode] != null){
            if(hashArray[hashCode].getKey() == key){
                Item temp = hashArray[hashCode];
                hashArray[hashCode] = null;
                return temp;
            }
            ++hashCode;
            hashCode %= arraySize;
        }
        return null;
    }
    //查找
    public Item find(int key){
        int hashCode = hash(key);
        while(hashArray[hashCode] != null){
            if(hashArray[hashCode].getKey() == key)
                return hashArray[hashCode];
            ++hashCode;
            hashCode %= arraySize;
        }
        return null;
    }
}
//定义哈希表中存放的数据类型，可以为任意的类型
class Item{
    int idata;
    public Item(int idata){
        this.idata = idata;
    }
    public int getKey(){
        return idata;
    }
}