Java集合框架分析（七）——自己实现hash表_JAVA_编程开发_程序员俱乐部

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

class="java">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方法
	 */
	public void rehash() {
		// 表的长度
		int oldCapacity = container.length;
		// 扩容后表的长度
		int newCapacity = oldCapacity * 2 + 1;
		// 新建一个新长度的哈希表
		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有了一些了解了。明天继续搞布隆过滤器。

?

?

?

?

?

?

?

?