HashMap 原理分析

hashmap的底层结构如上图所示，主要是数组和链表组成。

当我们创建一个hashmap对象之后，调用put方法的时候，首先通过key获取到一个hash值也就是hashcode，然后还会获取到一个所在数组的下标index，算法是：

hashcode = key.hashcode();

index = hashcode%数组长度-1；

然后将得到的hashcode、index、key和value存入一个entry对象当中。然后在将这个entry存入对应的数组位置上。但是通过上边的hashcode底层原理图会出现一个问题，就是如果一个位置上已经存在一个entry了，但是现在又有一个entry也要存到这个位置上边，应该怎么实现呢？这里我们就要用到链表结构，在entry对象中在放入一个链表（node）的next属性。这样我们就可以在同一个位置上存储多个entry了。

但是还有一个问题，就是数组的扩容问题，当一个数组的长度到一定值的时候，就需要扩大数组的容量，这个值为：

int 数组扩容阈值=数组原长度*0.75；

如果到了这个阈值就需要扩充数组的长度。但是这个时候就会出现问题。比如之前在数组下标为4位置上的entry在扩容之后，根据 index获取公式，它可能会到别的位置上，比如19上边去。这是就会造成，在调用get方法的时候，返回为null。这就是为什么说hashmap是线程非安全的。

下面上代码：

/**
 * 自定义map接口
 */
public interface Map<K,V> {

	public V put(K k,V v);
	
	public V get(K k);
	
	public int size();
	
	interface Entry<K,V>{
		public K getKey();
		public V getValue();
	}
}

/**
 * 
* @ClassName: HashMap
* @Description: 自定义hashmap类  实现自定义的map接口
* @author hsd
* @date 2019年3月8日
*
 */
public class HashMap<K,V> implements Map<K,V>{
	
	// map的底层是数组加链表，所以这里先定义一个数组
	private Entry[] table = null;
	// 数组初始化长度
	private static int defaultLength = 16;
	// 需要扩容的加载因子，  当数组的容量（数据长度size）为16*0.75=12的时候，数组就需要扩容
	private static double defaultLoader=0.75d;
	
	private int size = 0;
	
	public HashMap(){
		this(defaultLength,defaultLoader);
	}
	
	public HashMap(int length,double loader) {
		defaultLength = length;
		defaultLoader = loader;
		table = new Entry[defaultLength];

	}

	@Override
	public V put(K k, V v) {
		// 获取元素所在数组的位置，也就是数组的下标。
		int index = hash(k);
		Entry<K,V> entry = table[index];
		if(entry == null){
			table[index] = addEntry(index,k,v,null);
			size ++;
		} else{
			table[index] = addEntry(index,k,v,entry);
		}
		
		return (V) table[index].getValue();
	}
	
	
	
	
	private Entry<K,V> addEntry(int hash,K k, V v, Entry next) {
		
		return new Entry<K,V>(k,v,next,hash);
		
	}

	public int hash(K k){
		int index = k.hashCode()%defaultLength-1;
		return Math.abs(index);
	}

	@Override
	public V get(K k) {
		System.out.println("这是自己手写的hashmap");
		Entry<K,V> entry = getEntry(k);
		
		return entry == null?null:entry.getValue();
	}

	private Entry<K, V> getEntry(K k) {
		if(size == 0){
			return null;
		}
		
		int hash = hash(k);
		for(Entry e = table[hash];e!=null;e=e.next){
			if(e.hash == hash && (k==e.getKey() || k.equals(e.getKey()))){
				return e;
			}
		}
		return null;
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return size;
	}
	
	class Entry<K,V> implements Map.Entry<K, V>{
		
		K k;
		
		V v;
		
		Entry<K,V> next;
		// 每个数组位置放的数据的hashcode值
		int hash;
		
		

		public Entry(K k, V v,Entry<K, V> next, int hash) {
			this.k = k;
			this.v = v;
			this.next = next;
			this.hash = hash;
		}

		@Override
		public K getKey() {
			// TODO Auto-generated method stub
			return k;
		}

		@Override
		public V getValue() {
			// TODO Auto-generated method stub
			return v;
		}
		
	}

}

// 自写的map测试类
public class MapTest {

	public static void main(String[] args) {
		Map<String,String> map = new HashMap<String,String>();
		map.put("kobe","永远的24号");
		map.put("iverson","永远的3号");
		System.out.println(map.get("kobe"));
	}
	
	
}

代码中有一点需要注意的是，在entry中存储的写成了index，而不是hashcode，自己可以修改一下。

还有一点问题是，hashmap在jdk1.8之后，加入了红黑树来做链表那块的处理。优化了hashmap。

HashMap 原理分析

相关推荐