Java集合框架分析（七）——自己实现hash表

     开始之前先吐槽一下，妈蛋实现代码花了一个小时，调试起码花了一晚上，终于在这时候差不多了。和jdk的对比了下，10W以下的数据还好，10W以上就开始差别大了。不管怎么说还是实现了。原先是想把HashMap的源码分析一起弄上来的不过在实现的过程中就差不多把源码分析一遍了，其他小伙伴很多都分析了就不再出博客分析了，直接上代码：

package com.hash.demo;


/**
 * 自己实现一个hash表，参考了jdk的HashMap的源码
 * 
 * @author Linhaoxinag
 * 
 * @param <K>
 *            元素key值的类型
 * @param <V>
 *            元素value的类型
 */
public class MyHashMap<K, V> {

	// 定义初始容量
	private static int INITIAL_CAPACITY = 16;
	// 表内元素个数
	private int size = 0;
	// 一个哈希表的数据结构
	private Entry<K, V>[] container;
	// 自定义的负载因子
	private static float loadfactory = 0.75f;
	// 负载=负载因子*表的容量
	private int threshold;

	// 设置容量和负载因子的构造函数
	public MyHashMap(int capacity, float loadFactor) {

		this.loadfactory = loadFactor;
		threshold = (int) (capacity * loadfactory);
		this.INITIAL_CAPACITY = capacity;
		container = new Entry[INITIAL_CAPACITY];
	}

	// 默认构造函数
	public MyHashMap() {
		this(INITIAL_CAPACITY, loadfactory);
	}

	/**
	 * 插入元素的方法
	 * 
	 * @param k
	 *            插入元素的key值
	 * @param v
	 *            插入元素的value值
	 */
	public boolean put(K k, V v) {
		// 计算传入元素的key的hash值
		int hash = k.hashCode();
		// 得到在表中的索引
		int index = indexFor(hash, container.length);
		//Entry<K, V> e = container[index];
		for (Entry<K, V> e = container[index]; e != null; e = e.next) {
			if (e.hash == hash && ((e.key) == k || k.equals(e.key))) {
				
				e.value = v;
				return false;
			}

		}
		// 若没有相同的key值，就将新的添加到索引位置
		
		addEntry(hash, k, v, index);
		// 表内元素个数加1
		size++;
		return true;
	}

	/**
	 * 通过key值删除元素的方法
	 * 
	 * @param k
	 *            要删除元素的key值
	 */
	public Entry<K,V> remove(K k) {
		//计算hash值
		int hash = k.hashCode();
		//计算索引值
		int index = indexFor(k.hashCode(), container.length);
		//得到表中索引的元素
		Entry<K, V> e = container[index];
		//删除链表中键值为k的元素
		while (e != null) {
			if (e.hash == hash && ((e.key) == k || k.equals(e.key))) {
				// e = null;
				size--;
			}

			else {
				e = e.next;
			}

		}
			return e;
	}

	/**
	 * 通过key值来得到相应的value
	 * 
	 * @param k
	 *            要得到的元素的key值
	 * 
	 * @return 返回value
	 */
	public V get(K k) {

		// 计算hash值
		int hash = k.hashCode();
		// 计算索引值
		int index = indexFor(hash, container.length);
		// 在hash对应值的链表上查找键值为key的元素
		for (Entry<K, V> e = container[index]; e != null; e = e.next) {
			// 若相等就返回value值
			if (e.hash == hash && ((e.key) == k || k.equals(e.key)))
				return e.value;
		}
		// 没有就返回null
		return null;

	}

	/**
	 * 当哈希表超过负载时的rehash方法
         *  @param newCapacity  新的  哈希表容量，我们设置为原先的两倍
	 */
	public void rehash(int newCapacity) {
		// 表的长度
		int oldCapacity = container.length;
		// 新建一个新长度的哈希表
		Entry[] newContainer = new Entry[newCapacity];
		// 将原先hash表中的元素放入新的表中，并进行重新索引分布
		for (int i = 0; i < newCapacity; i++) {
			Entry<K, V> e = container[i];
			while (e != null) {
				Entry<K, V> next = e.next;
				// 重新计算每个数据的索引值
				int index = indexFor(e.hashCode(), newCapacity);
				// 将原先在链表上的元素放入新的数组中，使hash表均匀分布
				e.next = newContainer[index];

				newContainer[index] = e;
				e = next;
			}

		}
		container = newContainer;
		// 重新设置负载
		threshold = (int) (newCapacity * loadfactory);

	}

	/**
	 * 通过hash算法得到的hash值来计算出在表中的索引位置
	 * 
	 * @param hashcode
	 *            我们暂时就用jdk的hashcode方法来当我们的hash算法
	 * @param length
	 *            哈希表的长度
	 * @return 表中的索引位置
	 */

	public int indexFor(int hashcode, int length) {

		return hashcode & (length - 1);
	}

	/**
	 * 添加一个key-value对到表中
	 * 
	 * @param hash
	 *            经过hash算法得到的hash值
	 * @param k
	 *            元素的key值
	 * @param v
	 *            元素的value值
	 * @param index
	 *            通过indexFor计算出来的在表中的索引位置
	 */
	public void addEntry(int hash, K k, V v, int index) {
		Entry<K, V> e = container[index];
		container[index] = new Entry(hash, k, v, e);

	}
	

}

/**
 * 哈希表的数据结构 包括每个元素节点的key,value,next,和通过hash算法得到的hash值
 * 
 * @author linhaoxiang
 * 
 * @param <K>元素的key值
 * @param <V>元素的value值
 * 
 * 
 */
class Entry<K, V> {

	Entry<K, V> next;
	K key;
	V value;
	int hash;

	Entry(int h, K k, V v, Entry<K, V> n) {
		value = v;
		next = n;
		key = k;
		hash = h;
	}

}

以5W级为例，测试结果如下：

public class Test {  
	  
    public static void main(String[] args) {  
    	MyHashMap<String,String> mm = new MyHashMap<String,String>();   
        Long aBeginTime=System.currentTimeMillis();//记录BeginTime  
        for(int i=0;i<50000;i++){  
        mm.put(""+i, ""+i*32);  
        }  
        Long aEndTime=System.currentTimeMillis();//记录EndTime  
        System.out.println("insert time-->"+(aEndTime-aBeginTime));  
          
        Long lBeginTime=System.currentTimeMillis();//记录BeginTime  
        System.out.println(mm.get(""+1000));  
        Long lEndTime=System.currentTimeMillis();//记录EndTime  
        System.out.println("seach time--->"+(lEndTime-lBeginTime)); 
        mm.remove(""+100);
        System.out.println(mm.get(""+100)==null); 
        
        
    }  
}

insert time-->4761
32000
seach time--->0

 和jdk的比较

insert time-->141
32000
seach time--->0

 直接被虐成渣。。。。。还要继续优化，但不管怎么说今天一整天从早到晚分析了一遍hash，再自己实现了下，大体对hash有了一些了解了。明天继续搞布隆过滤器。

 补：今天反复又看了下代码，才发现漏了一个重要的东西！！！！在addEntry()方法里忘记把超过负载时调用rehash()这行代码加进去了！！！难怪时间差那么多，哈希表本来就是用空间换时间，漏了这句就等于失去哈希表的意义了妈蛋，赶紧加上再测试了下，终于ok了。

public void addEntry(int hash, K k, V v, int index) {
		Entry<K, V> e = container[index];
		container[index] = new Entry(hash, k, v, e);
		if (size++ >= threshold)
			rehash(2 * container.length + 1);

	}

 这是百万级的测试结果：

insert time-->720

seach time--->0

 虽然还是和jdk差了几倍但是没有昨天那么离谱了