HashMap源码分析——实现简易的hashmap

HashMap源码分析

• jdk1.7 HashMap源码分析
• • HashMap底层是怎样实现的
  • 关于如何转换数据结构的形态
  • 图片解释
  • 根据思路实现源码

jdk1.7 HashMap源码分析

HashMap底层是怎样实现的

HashMap 的底层是如何实现的？

jdk1.7以前是数组和链表 实现的

jdk1.8以后是 数组、链表、红黑树 实现的

一句话概括:

put的时候 会先通过哈希算法 算出 put进去的值的位置 再将值 以数组或链表或红黑数的结构 设置到对应的位置。

伪代码表示为

put(key,value)
{
  	  hash(key)
  	  index=hash&(n-1)
 }

例如  put进来一个 值  "a"   会先取值 "a" 的hashCode 然后 %15  这个时候可以算出一个索引位置 如 2
假设此时的数据结构是数组形式的 ， HashMap 会将 "a" 放入 element[2] 的位置
           

关于如何转换数据结构的形态

有同学可能会问了 :不是说数组,链表。红黑树么。 怎么光有数组?
           

数据结构什么时候从数组转变成链表呢?

答案是: 当 发生hash碰撞的时候

即 现在有两个key 他们的哈希值算出来的值 的 index位置都在 3 这个位置上 则代表此时发生了 哈希碰撞

此时 数组 3位置上 的数据将变为链表形式。 最开始存进去的值的 next 会指向 另一个key

图片解释

以上图片为jdk7 hashMap的 put 与get 的实现方式

根据思路实现源码

先定义一个Map接口

public interface Map<K,V> {
	
	V put(K k,V v); //定义一个 put方法
	V get(K k); //定义一个 get方法
	int size();  
	
	//定义一个 entry接口 方便遍历， java 里面只要是list 基本都实现了 entry接口
	interface Entry<K,V>{
		K getKey(); //返回key
		V getValue(); //返回value
		
	}
	
}
           

再定义实现类

public class HashMap<K, V>  implements Map<K, V>{
	
	private Entry<K,V>[] table=null;
	
	
	int size=0;
	
	
	public HashMap() {
		 table = new Entry[16];  //这里是jdk1.7 的实现，  jdk1.8里 是 懒汉式的。 只有put的时候 才会真正的初始化
	}
	
	/***
	 * @see 通过key 进行hash
	 * 取模 16
	 * 放到数组中去 
	 * 判断当前数组下标：
	 * 	没有值  则直接存入
	 *  有值，  则 用链表 存入 next
	 * 
	 */
	@Override
	public V put(K k, V v) {
		int index=hash(k);
		Entry<K,V> entry=table[index];
		
		if(null==entry) {
			table[index]=new Entry<>(k, v, k.hashCode(), null); 
		}else {
			table[index]=new Entry<>(k, v, k.hashCode(), entry); 
		}
		
		size++;
		
		return v;
	}

	private int hash(K k) {
		int i=k.hashCode()%16;
		return Math.abs(i);
	}

	@Override
	public V get(K k) {
		if(size==0) return null;
		
		int index=hash(k);
		
		if(null==table[index]) return null;
		
		Entry<K,V> entry=findValue(k, table[index]);
		
		
		return entry==null?null:entry.getValue();
	}
	
	/***
	 * @see 递归获取链表内的值，  
	 * @param k
	 * @param entry
	 * @return
	 */
	private  Entry<K, V> findValue(K k, Entry<K, V> entry) {
		if(entry.getKey().equals(k)||entry.getKey()==k) {
			return entry;
		}else {
			//判断next是否为空
			if(entry.next!=null) {
				return findValue(k, entry.next);
			}
		}
		return null;
		
	}

	@Override
	public int size() {
		return size;
	}
	
	class Entry<K, V> implements Map.Entry<K, V>{
		K k;
		V v;
		int hash;
		Entry<K,V> next;
		
		
		
		
		public Entry(K k, V v, int hash,  Entry<K, V> next) {
			super();
			this.k = k;
			this.v = v;
			this.hash = hash;
			this.next = next; 
		}

		@Override
		public K getKey() {
			return k;
		}

		@Override
		public V getValue() {
			return v;
		}
		
	}

}