hashset 和 hashmap 没本质区别, hashset 用的就是 hashmap 的 key 集, value 用 PRESENT(一个垃圾值) 填充.

hash
即散列, 就是把任意长度的输入, 通过散列算法(笔记最下面), 变换成固定长度的输出, 该输出就是散列值, 它的好处是便于查找(速度快).

hashmap 实现机制
数组 + 链表(数组的元素是链表).

数组的 size 默认是 16, 获得对象的 hash 后, 与 0xF 进行 “与” 运算, 找到数组的下标, 然后遍历该下标里的链表, 找到合适的位置插入/读取元素.

这个数组是可以 resize() 的, 当数组的 threshold 达到 0.75 后就会 resize(), 每次 resize() 是成倍数的增加, 16 -> 32.

重复的判定条件?
判断 hashmap/set 中的对象是否为同一个对象是通过三点来判断的:
o1.hash == o2.hash && ((o1 == o2) || (o1.equals(o2)))

• 判断对象的 hash 是否相同
• 判断是否为同一个对象(即 == 号, 判断两个对象的内存地址是否相同)
• 判断是否 equals

散列算法
h = key.hashCode() ^ (h >>> 16)

即取得对象的 hashCode 后先右移 16 位, 然后再和原始的 hashCode 进行异或运算, 这样做的目的是为了让对象的 hashcode 的高位和低位都进行运算, 保证其均匀分布.

何时重写 hashcode?
一般是配合 HashSet、HashMap 使用, 否则单独重写 equals 就可以了.