HashMap 原理分析

拼搏现实的明天。 2022-03-11 16:50 201阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ROVF9E_size_16_color_FFFFFF_t_70][]

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。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ROVF9E_size_16_color_FFFFFF_t_70]: /images/20220311/bdb599f43a5d4bf5bcbb431cd5294cca.png