哈希表的实现 博客分类： 数据结构 哈希表hash

实现一个哈希表，首先我们要知道哈希表可以干什么，包含什么方法，实现哪些功能。

哈希表又叫散列表，是根据关键码值(Key， value)而直接进行访问的数据结构。oracle文档里面提到，用哈希表进行检索和存储，key首先要完成hashcode方法，以确定这个key属于哪个区间，也就是说具有相同hashcode的被放在同一块区间里，hashcode往往是取模得出的结果。

确定了位置，我们还要解决冲突问题，如果表中已经存在当前要存的key，我们应该先删除以前的那个key，先后把新的key加入到表中，这里我们要做两步，判断是否存在相同的key，如果存在就删除以前的key，注意的是这里说的key实际上是<key, value>对。

实现代码如下

import java.util.LinkedList;

public class HashDemo<K, V> {
	private final int MAX_SIZE = 50;
	LinkedList<Element<K,V>>[] items;
	
	public HashDemo() {
		items = new LinkedList[MAX_SIZE];
	}
	
	/* 官方实现hashcode代码
    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }
	*/
	public int hashCodeOfKey(K Key) {
		return Key.toString().length() % items.length;
	}
	
	public void put(K key, V value) {
		int h = hashCodeOfKey(key);
		if(items[h] == null) 
			items[h] = new LinkedList<Element<K,V>>();
			//检查当前的key是否已经存在
			LinkedList<Element<K, V>> coll = items[h];
			for(Element<K,V> e : coll) {
				//如果存在就删除以前的元素
				if(e.equivalent(key)) {
					coll.remove(e);
					break;
				}
			}
			//把新的元素加到表中
			Element<K, V> element = new Element<K, V>(key, value);
			coll.add(element);
		}
	
	public V get(K key) {
		int h = hashCodeOfKey(key);
		if(items[h] == null) {
			return null;
		}
		LinkedList<Element<K, V>> coll = items[h];
		for(Element<K,V> e : coll) {
			if(e.equivalent(key)) 
				return e.getValue();
			
		}
		return null;
	}
}

//Element类帮助我们处理表中的元素
class Element<K, V> {
	private K key;
	private V value;
	public Element( K key, V value) {
		this.key = key;
		this.value = value;
	}
	
	public boolean equivalent(K k) {
		return key.equals(k);
	}
	
	public K getKey() {
		return key;
	}
	public V getValue() {
		return value;
	}	
}

参考资料：Cracking the Coding Interview，Gayle Laakmann McDowell