HashMap底层源码分析

迷南。 2021-12-03 15:11 308阅读 0赞

面试的时候经常会遇见诸如：“java中的HashMap是怎么工作的”，“HashMap的get和put内部的工作原理”这样的问题。本文将用一个简单的例子来解释下HashMap内部的工作原理。每当hashmap扩容的时候需要重新去add Entry对象，需要重新hash，然后放入我们新的entry table数组里面。如果在工作中，已经知道hashmap需要存多少值，几千或者几万的时候，最好新指定题目的扩容大小，防止在put的时候进行再次扩容很多次。

一、源码分析

1、初始化参数

在hashmap中我们必须要知道的参数有：初始化容量大小，默认是1 << 4，也就是16，

static final int DEFAULT\_INITIAL\_CAPACITY = 1 << 4;

加载因子0.75f，

static final float DEFAULT\_LOAD\_FACTOR = 0.75f;

hash在什么时候扩容？

put的时候会去做扩容，当大于3/4的时候就会。偶数扩容  ，  2\*16    2\*32   2\*64

2、put方法

public V put(K key, V value) {
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key);
            int i = indexFor(hash, table.length);
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
     
            modCount++;
            addEntry(hash, key, value, i);
            return null;
        }

对key做null检查。如果key是null，会被存储到table\[0\]，因为null的hash值总是0。

key的hashcode()方法会被调用，然后计算hash值。hash值用来找到存储Entry对象的数组的索引。有时候hash函数可能写的很不好，所以JDK的设计者添加了另一个叫做hash()的方法，它接收刚才计算的hash值作为参数。如果你想了解更多关于hash()函数的东西，可以参考：hashmap中的hash和indexFor方法  
indexFor(hash,table.length)用来计算在table数组中存储Entry对象的精确的索引。  
如果两个key有相同的hash值(也叫冲突)，他们会以链表的形式来存储。所以，这里我们就迭代链表。  
如果在刚才计算出来的索引位置没有元素，直接把Entry对象放在那个索引上。  
如果索引上有元素，然后会进行迭代，一直到Entry->next是null。当前的Entry对象变成链表的下一个节点。  
如果我们再次放入同样的key会怎样呢？逻辑上，它应该替换老的value。事实上，它确实是这么做的。在迭代的过程中，会调用equals()方法来检查key的相等性(key.equals(k))，如果这个方法返回true，它就会用当前Entry的value来替换之前的value。

对于put的值，我们可以来看一个例子：

public class demo {
        
        public static void main(String[] args) {
             HashMap hashMap=new HashMap<String, String>();
             Object put1 = hashMap.put("aa", "30");
             Object put2 = hashMap.put("aa", "31");
             System.out.println(put1+":"+put2);
        }
    }

当put两个相同的key的时候，这个put返回的值是oldValue,也就是说我这里打印出来的 结果就是  null：30

put返回的值是oldValue。key一样value会覆盖

如果hash key重复，value是不会覆盖的（经过hash算法返回的值如果重复了）。

对key进行hash处理的时候其实也是进行的位移处理，我们来看到hash的源码。

final int hash(Object k) {
            int h = hashSeed;
            if (0 != h && k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
     
            h ^= k.hashCode();
     
            // This function ensures that hashCodes that differ only by
            // constant multiples at each bit position have a bounded
            // number of collisions (approximately 8 at default load factor).
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }

3、get方法

当你传递一个key从hashmap总获取value的时候：对key进行null检查。如果key是null，table\[0\]这个位置的元素将被返回。  
key的hashcode()方法被调用，然后计算hash值。  
indexFor(hash,table.length)用来计算要获取的Entry对象在table数组中的精确的位置，使用刚才计算的hash值。  
在获取了table数组的索引之后，会迭代链表，调用equals()方法检查key的相等性，如果equals()方法返回true，get方法返回Entry对象的value，否则，返回null。

public V get(Object key) {
            if (key == null)
                return getForNullKey();
            Entry<K,V> entry = getEntry(key);
            return null == entry ? null : entry.getValue();
        }

final Entry<K,V> getEntry(Object key) {
            if (size == 0) {
                return null;
            }
     
            int hash = (key == null) ? 0 : hash(key);
            for (Entry<K,V> e = table[indexFor(hash, table.length)];
                 e != null;
                 e = e.next) {
                Object k;
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            }
            return null;
        }

4、Entry

hashmap table  :数组+链接   的数据结构

![槑槑,JAVA,自动化测试,微服务,框架,技术][JAVA]

void resize(int newCapacity) {
            Entry[] oldTable = table;
            int oldCapacity = oldTable.length;
            if (oldCapacity == MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return;
            }
    //创建Entry对象的数组
            Entry[] newTable = new Entry[newCapacity];
    //赋值
            transfer(newTable, initHashSeedAsNeeded(newCapacity));
            table = newTable;
            threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
        }

二、手写hashmap

通过前面的内容，我们已经知道了hashmap的原理了，我们现在来自己写一个hashmap。

1、map接口

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

2、实现类

public class HashMap<K,V>  implements Map<K, V> {
     
    	//初始容量
    	private static int defaultLength=16;   
    	//加载因子
    	private static double defaultLoader=0.75;
    	private Entry[]  table=null;
    	private int size=0;
     
    	
    	public HashMap() {
    		this(defaultLength, defaultLoader);
    	}
     
    	public HashMap(int length,double loader){
    		defaultLength=length;
    		defaultLoader=loader;
    		table=new Entry[defaultLength];
    	}
    	
    	
     
    	public HashMap(Entry[] table, int size) {
    		super();
    		this.table = table;
    		this.size = size;
    	}
     
    	public V put(K k, V v) {
    		size++;
    		int index=hash(k);
    		Entry<K, V>  entry=table[index];
    		if(entry==null){
    			table[index]=newEntry(k,v,null);
    		}else{
    			table[index]=newEntry(k,v,entry);
    		}
    		return  (V)table[index].getValue();
    	}
     
    	private Entry<K,V> newEntry(K k, V v, Entry<K, V> next) {
    		return new Entry(k, v, next);
    	}
     
    	public int hash(K k){
    		int m=defaultLength;
    		int i=k.hashCode()%m;
    		return i>=0?i:-i;
    	}
    	
    	
    	
    	
    	public V get(K k) {
    		int index=hash(k);
    		if(table[index]==null){
    			return null;
    		}
    		//在数组中查找
    		return find(k,table[index]) ;
    	}
     
    	public V find(K k, Entry entry) {
    		if(k==entry.getKey() || k.equals(entry.getKey())){
    			
    			if(entry.next!=null){
    				//System.out.println("1oldValue:"+entry.next.getValue());	
    			}
    			
    			
    			return  (V) entry.getValue();
    		}else{
    			if(entry.next!=null){
    				//System.out.println("2oldValue:"+entry.next.getValue());
    				return find(k, entry.next);
    			}
    		}
    		return null;
    	}
     
    	public int size() {
    		
    		return size;
    	}
    	
    	class Entry<K,V>  implements  Map.Entry<K, V>{
     
    		K k;
    		V v;
    		Entry<K,V>  next;
    		
    		public Entry(K k, V v, Entry<K, V> next) {
    			super();
    			this.k = k;
    			this.v = v;
    			this.next = next;
    		}
     
    		public K getKey() {
    			
    			return k;
    		}
     
    		public V getValue() {
    			
    			return v;
    		}
     
    		public K getK() {
    			return k;
    		}
     
    		public void setK(K k) {
    			this.k = k;
    		}
     
    		public V getV() {
    			return v;
    		}
     
    		public void setV(V v) {
    			this.v = v;
    		}
     
    		public Entry<K, V> getNext() {
    			return next;
    		}
     
    		public void setNext(Entry<K, V> next) {
    			this.next = next;
    		}
    		
    	}
    	
    }

3、通过一个main函数，来测试一下，我们写的这个hashmap是否正确。

public static void main(String[] args) {
    		Map<String, Integer> map=new HashMap<String,Integer>();
    		map.put("sss", 30);
    		map.put("sss", 31);
    		System.out.println(map.get("sss"));
    	}

注意，引入包的时候要注意，不要引入jdk框架的map和hash包，要引入我们自己写的这个包。

HashMap有一个叫做Entry的内部类，它用来存储key-value对。  
上面的Entry对象是存储在一个叫做table的Entry数组中。  
table的索引在逻辑上叫做“桶”(bucket)，它存储了链表的第一个元素。  
key的hashcode()方法用来找到Entry对象所在的桶。  
如果两个key有相同的hash值，他们会被放在table数组的同一个桶里面。

[JAVA]: /images/20211203/f0253d7b978a4323bec1dfebfb6ad7ab.png