哈希表
TreeMap分析
时间复杂度（平均） 添加、删除、搜索：O(logn)
特点 Key 必须具备可比较性 元素的分布是有顺序的
在实际应用中，很多时候的需求 Map 中存储的元素不需要讲究顺序 Map 中的 Key 不需要具备可比较性
不考虑顺序、不考虑 Key 的可比较性，Map 有更好的实现方案，平均时间复杂度可以达到 O(1) 那就是采取哈希表来实现 Map
哈希表（Hash Table）
添加、搜索、删除的流程都是类似的
- 利用哈希函数生成 key 对应的 index【O(1)】
- 根据 index 操作定位数组元素【O(1)】
哈希表是【空间换时间】的典型应用 哈希函数，也叫做散列函数
哈希表内部的数组元素，很多地方也叫 Bucket（桶），整个数组叫 Buckets 或者 Bucket Array
哈希冲突（Hash Collision）
解决哈希冲突的常见方法
- 开放定址法（Open Addressing） :按照一定规则向其他地址探测，直到遇到空桶
- 再哈希法（Re-Hashing） : 设计多个哈希函数
- 链地址法（Separate Chaining） : 比如通过链表将同一index的元素串起来
JDK1.8的哈希冲突解决方案
默认使用单向链表将元素串起来
在添加元素时，可能会由单向链表转为红黑树来存储元素 比如当哈希表容量 ≥ 64 且 单向链表的节点数量大于 8 时
当红黑树节点数量少到一定程度时，又会转为单向链表
JDK1.8中的哈希表是使用链表+红黑树解决哈希冲突
思考：这里为什么使用单链表？ 每次都是从头节点开始遍历 单向链表比双向链表少一个指针，可以节省内存空间
哈希函数
哈希函数的实现步骤大概如下
-
先生成 key 的哈希值（必须是整数）
-
再让 key 的哈希值跟数组的大小进行相关运算，生成一个索引值
为了提高效率，可以使用 & 位运算取代 % 运算【前提：将数组的长度设计为 2 的幂（2 n ）】
良好的哈希函数 让哈希值更加均匀分布 → 减少哈希冲突次数 → 提升哈希表的性能
如何生成key的哈希值
key 的常见种类可能有整数、浮点数、字符串、自定义对象
不同种类的 key，哈希值的生成方式不一样，但目标是一致的
尽量让每个 key 的哈希值是唯一的 尽量让 key 的所有信息参与运算
在Java中，HashMap 的 key 必须实现 hashCode、equals 方法，也允许 key 为 null
整数 :整数值当做哈希值 比如 10 的哈希值就是 10
浮点数 :将存储的二进制格式转为整数值
Long和Double的哈希值:高32bit 和 低32bit 混合计算出 32bit 的哈希值,(>>> 和 ^)
字符串:
关于31的探讨
31不仅仅是符合2^n – 1，它是个奇素数（既是奇数，又是素数，也就是质数）
素数和其他数相乘的结果比其他方式更容易产成唯一性，减少哈希冲突
最终选择31是经过观测分布结果后的选择
自定义对象作为key
自定义对象作为 key，最好同时重写 hashCode 、equals 方法
equals ：用以判断 2 个 key 是否为同一个 key
- 自反性：对于任何非 null 的 x，x.equals(x)必须返回true
- 对称性：对于任何非 null 的 x、y，如果 y.equals(x) 返回 true，x.equals(y) 必须返回 true
- 传递性：对于任何非 null 的 x、y、z，如果 x.equals(y)、y.equals(z) 返回 true，那么x.equals(z) 必须 返回 true
- 一致性：对于任何非 null 的 x、y，只要 equals 的比较操作在对象中所用的信息没有被修改，多次调用 x.equals(y) 就会一致地返回 true，或者一致地返回 false
- 对于任何非 null 的 x，x.equals(null) 必须返回 false
hashCode ：必须保证 equals 为 true 的 2 个 key 的哈希值一样 反过来 hashCode 相等的 key，不一定 equals 为 true
不重写 hashCode 方法只重写 equals 会有什么后果？ 可能会导致 2 个 equals 为 true 的 key 同时存在哈希表中
装填因子
装填因子（Load Factor）：节点总数量 / 哈希表桶数组长度，也叫做负载因子
在JDK1.8的HashMap中，如果装填因子超过0.75，就扩容为原来的2倍
TreeMap vs HashMap
何时选择TreeMap？ 元素具备可比较性且要求升序遍历（按照元素从小到大）
何时选择HashMap？ 无序遍历
LinkedHashMap
在HashMap的基础上维护元素的添加顺序，使得遍历的结果是遵从添加顺序的
关于使用%来计算索引
建议把哈希表的长度设计为素数（质数） 可以大大减小哈希冲突
不同数据规模对应的最佳素数，特点如下：每个素数略小于前一个素数的2倍 每个素数尽可能接近2的幂（2n ）
网友评论