面试的时候经常会遇见诸如:“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 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();
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 entry = getEntry(key); return null == entry ? null : entry.getValue(); }
final Entry getEntry(Object key) { if (size == 0) { return null; } int hash = (key == null) ? 0 : hash(key); for (Entry 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 :数组+链接 的数据结构
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 { public V put(K k,V v); public V get(K k); public int size(); public interface Entry{ public K getKey(); public V getValue(); }}
2、实现类
public class HashMap implements Map { //初始容量 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 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 newEntry(K k, V v, Entry 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 implements Map.Entry{ K k; V v; Entry next; public Entry(K k, V v, Entry 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 getNext() { return next; } public void setNext(Entry next) { this.next = next; } } }
3、通过一个main函数,来测试一下,我们写的这个hashmap是否正确。
public static void main(String[] args) { Map map=new HashMap(); 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数组的同一个桶里面。
---------------------------------------------------------------------------------------------------
文章出处:
http://blog.csdn.net/sdksdk0/article/details/79299286
作者:朱培 ID:sdksdk0
---------------------------------------------------------------------------------------------------