我要评论
目录
一.哈希表(散列)
1.什么是哈希表
2.什么是哈希冲突(面试题)
3.解决哈希冲突的方法(面试题)
(1) 开放地址法
hi=(h(key)+di)%m //开放地址法计算下标公式
hi：下标(储存的地址)
h(key)：哈希函数(计算哈希值)
di：增量
%：取模
m：哈希表的长度
探查方法如下
① 线性探查
②二次探查
③随机探查
为了更好的理解，我们举一个例子
设哈希表长为14，哈希函数为h(key)=key%11。表中现有数据15、38、61和84，其余位置为空，如果用二次探测再散列处理冲突，则49的位置是？使用线性探测法位置是？
解：因为h(key)=key%11
所以15的位置 = 15 % 11=4; 38的位置 = 38 % 11=5; 61的位置 = 61 % 11=6; 84的位置 = 84 % 11=7;(证明哈希表4,5,6,7已经有元素)
因为计算下标的公式为：hi=(h(key)+di)mod%m
使用二次探测法
h(1) = (49%11 + 1^1) = 6;冲突
h(-1) = (49%11 + (-1^2)) = 4;冲突 注意 -1^2 = -1; (-1)^2 = 1;
h(2) = (49%11 + 2^2) = 9;不冲突
二次探测法49的位置就是哈希表的9。
使用线性探测
h(1) = (49%11 + 1) = 6;冲突
h(2) = (49%11 + 2) = 7;冲突
h(3) = (49%11 + 3) = 8;不冲突
线性探测法49的位置就是哈希表的8。
(2) 再哈希法
(3) 链地址法
(4)建立公共溢出区
二.hashmap
1.hashmap的hash()算法(面试)
(1)为什么不是h = key.hashcode()直接返回，而要 h = key.hashcode() ^ (h >>> 16)来计算哈希值呢？
回答：减少哈希冲突
//源码：计算哈希值的方法 h(key)
static final int hash(object key) {
int h;
return (key == null) ? 0 : (h = key.hashcode()) ^ (h >>> 16);
}
//^ (异或运算) 相同的二进制数位上，数字相同，结果为0，不同为1。 举例如下：
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 1 = 0
1 ^ 0 = 1
// &(与运算) 相同的二进制数位上，都是1的时候，结果为1，否则为零。 举例如下：
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
h = key.hashcode() ^ (h >>> 16)意思是先获得key的哈希值h，然后 h 和 h右移十六位 做异或运算，运算结果再和 数组长度 - 1 进行 与 运算，计算出储存下标的位置。具体原理如下：
综下所述 储存下标 = 哈希值 & 数组长度 - 1
//jdk1.7中计算数组下标的hashmap源码
static int indexfor(int h, int length) {
//计算储存元素的数组下标
return h & (length-1);
}
//jdk1.8中去掉了indexfor()函数，改为如下
i = (n - 1) & hash //i就是元素存储的数组下标
某个key的哈希值为 ：1111 1111 1110 1111 0101 0101 0111 0101，数组初始长度也是16，如果没有 ^ h >>> 16，计算下标如下
1111 1111 1110 1111 0101 0101 0111 0101 //h = hashcode()
& 0000 0000 0000 0000 0000 0000 0000 1111 //数组长度 - 1 = 15 (15的二进制就是 1111)
------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 //key的储存下标为5
由上面可知，只相当于取了后面几位进行运算，所以哈希冲突的可能大大增加。
以上条件不变，加上 异或h >>> 16，之后在进行下标计算
1111 1111 1110 1111 0101 0101 0111 0101 //h = hashcode()
^ 0000 0000 0000 0000 1111 1111 1110 1111 //h >>> 16
------------------------------------------
1111 1111 1110 1111 1010 1010 1001 1010 //h = key.hashcode() ^ (h >>> 16)
& 0000 0000 0000 0000 0000 0000 0000 1111 //数组长度 - 1 = 15 (15的二进制就是 1111)
------------------------------------------
0000 0000 0000 0000 0000 0000 0000 1010 //key的存储下标为10
重要：由上可知，因为哈希值得高16位和低16位进行异或运算，混合之后的哈希值，低位也可能掺杂了高位的一部分特性(就是变化性增加了)，这样就减少了哈希冲突。
(2)为什么hashmap的初始容量和扩容都是2的次幂
回答：也是为了减少哈希冲突。
1111 1111 1110 1111 0101 0101 0111 0101 //hash值
& 0000 0000 0000 0000 0000 0000 0000 1111 //数组长度 - 1 = 15 (15的二进制就是 1111)
------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 //高位全部清零，只保留末四位(就相当于保留了hash的低位)
如果容量不是2次幂会怎么样呢？如下图表
- 2次幂的时候，数组长度为16，n-1 = 16 -1 = 15(1111)
| hash | (n-1) & hash | 储存下标 |
|---|---|---|
| 0 | 1111 & 0000 | 0 |
| 1 | 1111 & 0001 | 1 |
| 2 | 1111 & 0010 | 2 |
| 3 | 1111 & 0011 | 3 |
| 4 | 1111 & 0100 | 4 |
| 5 | 1111 & 0101 | 5 |
- 非2次幂的时候，数组长度为10，n-1 = 10 -1 = 9(1001)
| hash | (n-1) & hash | 储存下标 |
|---|---|---|
| 0 | 1001 & 0000 | 0 |
| 1 | 1001 & 0001 | 1 |
| 2 | 1001 & 0010 | 0 |
| 3 | 1001 & 0011 | 1 |
| 4 | 1001 & 0100 | 0 |
| 5 | 1001 & 0101 | 1 |
重要：由上看出，n为2的次幂，哈希冲突会更少，保证元素的均匀插入。
(3)如果指定了不是2的次幂的容量会发生什么？
回答：会获得一个大于指定的初始值的最接近2的次幂的值作为初始容量。
比如：输入 9 获得 16，输入 5 获得 8。
原理如下：
static final float default_load_factor = 0.75f; //负载因子
static final int maximum_capacity = 1 << 30;//初始容量最大为 2的30次方
/**
* @param initialcapacity 初始容量
*/
public hashmap(int initialcapacity) {
//此处通过把第二个参数负载因子使用默认值0.75f，然后调用有两个参数的构造方法
this(initialcapacity, default_load_factor);//调用函数一
}
/**
* 函数一
* @param initialcapacity 初始容量
* @param loadfactor 负载因子
*/
public hashmap(int initialcapacity, float loadfactor) {
if (initialcapacity < 0) //如果初始容量小于0，抛出异常
throw new illegalargumentexception("illegal initial capacity: " + initialcapacity);
if (initialcapacity > maximum_capacity) //如果初始容量超过最大容量（1<<30）
initialcapacity = maximum_capacity; //则使用最大容量作为初始容量
if (loadfactor <= 0 || float.isnan(loadfactor)) //如果负载因子小于等于0或者不是数字，则抛出异常
throw new illegalargumentexception("illegal load factor: " + loadfactor);
this.loadfactor = loadfactor; //把负载因子赋值给成员变量loadfactor
//调用tablesizefor方法计算出不小于initialcapacity的最小的2的幂的结果，并赋给成员变量threshold
this.threshold = tablesizefor(initialcapacity); //调用函数二
}
/**
* 函数二
* @param cap 初始容量
*/
static final int tablesizefor(int cap) { //这里我们假设我们初始容量是 10
//容量减1，为了防止初始化容量已经是2的幂的情况，在最后有n+1的操作。 n = 10 - 1 = 9
int n = cap - 1;
//n = (n | n >>> 1) 带入得 n = (1001 | 0100) = 1101
n |= n >>> 1;
//n = (n | n >>> 2) 带入得 n = (1101 | 0011) = 1111
n |= n >>> 2;
//n = (n | n >>> 4) 带入得 n = (1111 | 0000) = 1111
n |= n >>> 4;
//n = (n | n >>> 8) 带入得 n = (1111 | 0000) = 1111
n |= n >>> 8;
//n = (n | n >>> 16) 带入得 n = (1111 | 0000) = 1111 = 15
n |= n >>> 16;
/**
如果入参cap为小于或等于0的数，那么经过cap-1之后n为负数，n经过无符号右移和或操作后仍未负数,
所以如果n<0,则返回1;如果n大于或等于最大容量，则返回最大容量;否则返回n+1。
n = 15 + 1 = 16，咱们传进来是初始容量10，会自动转为16容量。
**/
return (n < 0) ? 1 : (n >= maximum_capacity) ? maximum_capacity : n + 1;
//return (n < 0) ? 1 : (n >= maximum_capacity) ? maximum_capacity : n + 1;相当于下面这段代码
if(n < 0){
return 1;
}else{
if(n >= maximum_capacity){
return maximum_capacity;
}else{
return n + 1;
}
}
}
2.hashmap为什么线程不安全(面试题)
(1) 多线程下扩容造成的死循环和数据丢失(jdk1.7)
① 假设这里有两个线程同时执行了put()操作(扩容)，并进入了transfer()方法。线程a先进行操作
② 线程a在执行到 newtable[i] = e后被挂起，因为 newtable[i] = null,又因为 e.next = newtable[i]，所以e.next = null
transfer()方法部分源码：
while(null !=e)
{
entry<k,v> next =e.next; //next = 3.next = 7
e.next = newtable[i]; //3.next = null
newtable[i] = e;//线程a执行到这里被挂起了
e = next;
}
③ 开始执行线程b，并完成了扩容。这时候 7.next = 3；3.next = null；
④ 继续执行线程a，执行 newtable[i] = e，因为当时 e = 3，所以将3放到对应位置，此时执行 e = next，因为 next = 7(第②步)，所以 e = 7
while(null !=e)
{
entry<k,v> next =e.next; //next = 3.next = 7
e.next = newtable[i]; //3.next = null
newtable[i] = e;//继续从这里执行 newtable[i] = 3
e = next; //e = 7
}
⑤ 上轮循环之后e=7，从主内存中读取e.next时发现主内存中7.next=3，此时next=3，并将7采用头插法的方式放入新数组中，并继续执行完此轮循环。
while(null !=e)
{
entry<k,v> next =e.next; //next = 7.next = 3
e.next = newtable[i]; //7.next = 3
newtable[i] = e;//newtable[i] = 7
e = next; //e = 3
}
⑥上轮循环7.next=3，而e=3，执行下一次循环可以发现，因为3.next=null，所以循环之后 e = null，所以循环会退出。
while(null !=e)
{
entry<k,v> next =e.next; // next = 3.next = null
e.next = newtable[i]; //3.next = 7 (此处3指向7,同时之前7也指向了3,所以会形成闭环)
newtable[i] = e; //newtable[i] = 3
e = next; //e = null(退出循环条件)
}
(2)数据覆盖(jdk1.8)
当你调用put()方法时，putval()方法里面有两处代码会产生数据覆盖。
3.hashmap解决线程不安全(面试题)
(1) 使用hashtable解决线程不安全问题(弃用)
(2)hashmap和hashtable的区别
①线程是否安全
hashmap线程不安全。
hashtable线程安全，但是效率较低。
②是否null
hashmap中key只能有一个null，value可以多个为null。
hashtable不允许键或值为null。
③容量
hashmap底层数组长度必须为2的幂（16，32，128…），默认为16。
hashtable底层数组长度可以为任意值，导致hash算法散射不均匀，容易造成hash冲突，默认为11。
④底层区别
hashmap是底层由数组+链表形成，在jdk1.8之后链表长度大于8时转化为红黑树。
hashtable一直都是数组+链表。
⑤继承关系
hashtable继承自dictionary类。
hashmap继承自abstractmap类。
(3)collections.synchronizedmap(不常用)
map<string,string> map = collections.synchronizedmap(new hashmap<>());
(4)concurrenthashmap(常用)
4.为什么使用synchronized替换reentrantlock锁呢？
① 减少内存开销。假设使用可重入锁来获得同步支持，那么每个节点都需要通过继承aqs(队列同步器)来获得同步支持。但并不是每个节点都需要获得同步支持的，只有链表的头节点（红黑树的根节点）需要同步，这无疑带来了巨大内存浪费。
② 获得jvm的支持。可重入锁毕竟是api这个级别的，后续的性能优化空间很小。 synchronized则是jvm直接支持的，jvm能够在运行时作出相应的优化措施：锁粗化、锁消除、锁自旋等等。这就使得synchronized能够随着jdk版本的升级而不改动代码的前提下获得性能上的提升。
③在 jdk1.6 中，对 synchronized 锁的实现引入了大量的优化，并且 synchronized 有多种锁状态，会从无锁 -> 偏向锁 -> 轻量级锁 -> 重量级锁一步步转换。
aqs：是一个队列同步器，同步队列是一个双向链表，有一个状态标志位state，如果state为1的时候，表示有线程占用，其他线程会进入同步队列等待，如果有的线程需要等待一个条件，会进入等待队列，当满足这个条件的时候才进入同步队列，reentrantlock就是基于aqs实现的
- 偏向锁：减少无竞争且只有一个线程使用锁的情况下，使用轻量级锁产生的性能消耗。轻量级锁每次申请、释放锁都至少需要一次cas，但偏向锁只有初始化时需要一次cas。
- 轻量级锁：当有两个线程，竞争的时候就会升级为轻量级锁。轻量级锁的目标是，减少无实际竞争情况下，使用重量级锁产生的性能消耗，包括系统调用引起的内核态与用户态切换、线程阻塞造成的线程切换等。
- 重量级锁：大多数情况下，在同一时间点，常常有多个线程竞争同一把锁，悲观锁的方式，竞争失败的线程会不停的在阻塞及被唤醒态之间切换，代价比较大。
4.hashmap底层 数组 + 链表 / 红黑树(面试题)
红黑树：平衡二叉查找树
(1)hashmap为什么引入链表
(2)hashmap为什么引入红黑树
(3)为什么不一开始就使用红黑树
(4)说说你对红黑树的理解
- 1.根节点是黑色
- 2.节点是黑色或红色
- 3.每个叶子节点是黑色
- 4.红色节点的子节点都是黑色
- 5.从任意节点到其叶子节点的所有路径都包含相同数目的黑色节点
说出以上就很好了
补充：以上性质强制了红黑树的关键性质从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。保证了红黑树的高效。
(5) 红黑树为什么要变色、左旋和右旋操作
5.hashmap链表和红黑树转换(面试题)
- 链表长度大于8，并且表的长度大于64 数组 + 红黑树
- 链表长度大于8，并且表的长度不大于64 数组 + 链表 会扩容
- 当数的节点小于6 数组 + 链表
(1) 为什么链表长度大于8，并且表的长度大于64的时候，链表会转换成红黑树？
in usages with well-distributed user hashcodes, tree bins
are rarely used. ideally, under random hashcodes, the
frequency of nodes in bins follows a poisson distribution
(http://en.wikipedia.org/wiki/poisson_distribution) with a
parameter of about 0.5 on average for the default resizing
threshold of 0.75, although with a large variance because
of resizing granularity. ignoring variance, the expected
occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
factorial(k)). the first values are:
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million //翻译：更多：少于千万分之一
负载因子是0.75和长度为8转为红黑树的原理：由上面我们可以看出 当负载因子为0.75时，哈希冲突出现的频率遵循参数为0.5的泊松分布。
常数0.5是作为参数代入泊松分布来计算的，而加载因子0.75是作为一个条件。
泊松分布是一种离散概率分布，泊松分布的概率质量函数：
x=(0,1,2,...)。
λ：单位时间内随机事件的平均发生率。因为我们从上面知道平均发生率是0.5
e^(-0.5) = 0.60653065971264 //e的负0.5次方
阶乘：指从1乘以2乘以3乘以4一直乘到所要求的数。比如 3！ = 1 * 2 * 3
- p(0) = (0.50 * e-0.5) / 0! ≈ 0.60653066
- p(1) = (0.51 * e-0.5) / 1! ≈ 0.30326533
- p(2) = (0.52 * e-0.5) / 2! ≈ 0.07581633
- 后面就不给大家计算了，有兴趣可以自己算一下。
(2) 为什么转成红黑树是8呢？而重新转为链表阈值是6呢？
(3) 为什么负载因子是0.75？
加载因子越大，填满的元素越多，空间利用率越高，但发生冲突的机会变大了；
加载因子越小，填满的元素越少，冲突发生的机会减小，但空间浪费了更多了，而且还会提高扩容rehash操作的次数。
“冲突的机会”与“空间利用率”之间，寻找一种平衡与折中。
6.hashmap扩容(面试题)
(1)什么时候会发生扩容？
(2)为什么不是满了扩容？
(3)扩容过程
-
jdk1.7
创建一个新的table，并调用transfer()方法把旧数组中的数据迁移到新数组中，使用的是头插法，也就是说，新table中链表的顺序和旧列表中是相反的，在hashmap线程不安全的情况下，这种头插法可能会导致死链和数据丢失现象。 -
jdk1.8
①在resize()方法中，定义了oldcap参数，记录了原table的长度，定义了newcap参数，记录新table长度，newcap是oldcap长度的2倍，然后循环原table，把原table中的每个链表中的每个元素放入新table。
②计算索引做了优化：hash（原始hash） & oldcap（原始容量） == 0 的元素留在原来位置 ，否则新位置 = 旧位置 + oldcap（原始容量）。
注意
-
扩容是一个特别耗性能的操作，所以当程序员在使用hashmap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
-
hashmap的容量达到2的30次方，就不会在进行扩容了。
发表评论