jdk7 中HashMap的知识点总结
hashmap中的几个重要变量
默认初始容量,必须是2的n次方
static final int default_initial_capacity = 16;
最大容量，当通过构造方法传入的容量比它还大时，就用这个最大容量，必须是2的n次方
static final int maximum_capacity = 1 << 30;
默认负载因子
static final float default_load_factor = 0.75f;
用来存储键值对，可以看到键值对都是存储在entry中的
transient entry<k,v>[] table; //capacity * load factor,超过这个数就会进行再哈希 int threshold;
hashmap中的元素是用名为table的entry数组来保存的，默认大小是16
- capacity:数组的容量
- load_factor:负载因子
- threshold：实际能承载的容量，等于上面两个相乘，当size大于threshold时，就会进行rehash
jdk7中在面对key为string的时候采用了区别对待，会有alternative hashing，但是这个在jdk8中已经被删除了
存储结构
entry是一个链表结构，不仅包含key和value，还有可以指向下一个的next
static class entry<k,v> implements map.entry<k,v> {
final k key;
v value;
entry<k,v> next;
int hash;
/**
* creates new entry.
*/
entry(int h, k k, v v, entry<k,v> n) {
value = v;
next = n;
key = k;
hash = h;
}
...
put方法
public v put(k key, v value) {
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;
}
首先通过hash方法对hashcode进行处理：
final int hash(object k) {
int h = 0;
h ^= k.hashcode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
可以看到只是在key的hashcode值上做了一些处理，通过hash计算出来的值将会使用indexfor方法找到它应该所在的table下标：
static int indexfor(int h, int length) {
return h & (length-1);
}
这个方法其实相当于对table.length取模。
当需要插入的key为null时，调用putfornullkey方法处理：
private v putfornullkey(v value) {
for (entry<k,v> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
v oldvalue = e.value;
e.value = value;
e.recordaccess(this);
return oldvalue;
}
}
modcount++;
addentry(0, null, value, 0);
return null;
}
putfornullkey方法只从table[0]这个位置开始遍历，因为key为null只放在table中的第一个位置，下标为0，在遍历中如果发现已经有key为null了，则替换新value，返回旧value，结束；如果还没有key为null，调用addentry方法增加一个entry:
void addentry(int hash, k key, v value, int bucketindex) {
if ((size >= threshold) && (null != table[bucketindex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketindex = indexfor(hash, table.length);
}
createentry(hash, key, value, bucketindex);
}
可以看到jdk7中resize的条件已经发生改变了，只有当 size>=threshold并且 table中的那个槽中已经有entry时，才会发生resize。即有可能虽然size>=threshold，但是必须等到每个槽都至少有一个entry时，才会扩容。还有注意每次resize都会扩大一倍容量
void createentry(int hash, k key, v value, int bucketindex) {
entry<k,v> e = table[bucketindex];
table[bucketindex] = new entry<>(hash, key, value, e);
size++;
}
最后看createentry，它先保存这个桶中的第一个entry，创建新的entry放入第一个位置，将原来的entry接在后面。这里采用的是头插法插入元素。
get方法
其实get方法和put方法如出一辙，怎么放的怎么拿
public v get(object key) {
if (key == null)
return getfornullkey();
entry<k,v> entry = getentry(key);
return null == entry ? null : entry.getvalue();
}
key为null时，还是去table[0]去取：
private v getfornullkey() {
for (entry<k,v> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
否则调用getentry方法：
final entry<k,v> getentry(object key) {
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;
}
这个方法也是通过key的hashcode计算出它应该所在的下标，再遍历这个下标的entry链，如果key的内存地址相等（即同一个引用）或者equals相等，则说明找到了
hash的原则
a、等幂性。不管执行多少次获取hash值的操作，只要对象不变，那么hash值是固定的。如果第一次取跟第n次取不一样，那就用起来很麻烦.
b、对等性。若两个对象equal方法返回为true，则其hash值也应该是一样的。举例说明：若你将obja作为key存入hashmap中，然后new了一个objb。在你看来objb和obja是一个东西（因为他们equal），但是使用objb到hashmap中却取不出来东西。
c、互异性。若两个对象equal方法返回为false，hash值有可能相同，但最好是不同的，这个不是必须的，只是这样做会提高hash类操作的性能（碰撞几率低）。
解决hash碰撞的方法：
- 开放地址法
- 链地址法
hashmap采用的就是链地址法，这种方法好处是无堆积现象，但是next指针会占用额外空间
和jdk8中的hashmap区别
在jdk8中，仍然会根据key.hashcode()计算出hash值，再通过这个hash值去定位这个key，但是不同的是，当发生冲突时，会采用链表和红黑树两种方法去处理，当结点个数较少时用链表（用node存储），个数较多时用红黑树（用treenode存储），同时结点也不叫entry了，而是分成了node和treenode。再最坏的情况下，链表查找的时间复杂度为o(n),而红黑树一直是o(logn),这样会提高hashmap的效率。jdk8中的hashmap中定义了一个变量treeify_threshold，当节点个数>= treeify_threshold - 1时，hashmap将采用红黑树存储
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流。