经常使用HashMap,但估计很少有人仔细研究过它,下面就HashMap聊一聊我的认识
一.实现原理
HashMap底层使用的是hash算法,那么Hash算法到底是什么算法呢?其实Hash算法有很多种.
哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。
hashmap采用的算法:除留余数法：
假设哈希表长为m，p为小于等于m的最大素数，则哈希函数为
h（k）=k % p ，其中%为模p取余运算。
例如，已知待散列元素为（18，75，60，43，54，90，46），表长m=10，p=7，则有
h(18)=18 % 7=4 h(75)=75 % 7=5 h(60)=60 % 7=4
h(43)=43 % 7=1 h(54)=54 % 7=5 h(90)=90 % 7=6
h(46)=46 % 7=4
此时冲突较多。为减少冲突，可取较大的m值和p值，如m=p=13，结果如下：
h(18)=18 % 13=5 h(75)=75 % 13=10 h(60)=60 % 13=8
h(43)=43 % 13=4 h(54)=54 % 13=2 h(90)=90 % 13=12
h(46)=46 % 13=7
此时没有冲突，如图1所示。
0 1 2 3 4 5 6 7 8 9 10 11 12
54
43
18
46
60
75
90
图1 除留余数法求哈希地址
二.存储原理
存储原理 : hashmap存储采用的是数组加链表的结构,采用除留余数法将原有的数据的hashcode值除以数组长度,根据余数获得散列,再存入对应的数组索引处,当不同的key对应的余数相同时,再采用链表结构,将相同余数的key存在同一个数组索引处.
图2 hashmap存储原理
三.扩容机制
话不多说,篓源码
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 默认初始数组长度 static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量 static final float DEFAULT_LOAD_FACTOR = 0.75f; //负载因子 int threshold; //The next size value at which to resize (capacity * load factor). 图3 扩容机制
以上是我对HashMap的一些认识,时间仓促,如有错误,请批评指正
