Skip to main content

hash-table

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

哈希算法的应用​

  • 安全加密 哈希算法可以对大数据做信息摘要，通过一个较短的二进制编码来表示很大的数据。
  • 唯一标识 校验数据的完整性和正确性。
  • 数据校验 任何哈希算法都会出现散列冲突，但是这个冲突概率非常小。越是复杂哈希算法越难破解，但同样计算时间也就越长。 所以，选择哈希算法的时候，要权衡安全性和计算时间来决定用哪种哈希算法。
  • 散列函数 散列表对哈希算法的要求非常特别，更加看重的是散列的平均性和哈希算法的执行效率。
  • 负载均衡 利用哈希算法替代映射表，可以实现一个会话粘滞的负载均衡策略。
  • 数据分片 通过哈希算法对处理的海量数据进行分片，多机分布式处理，可以突破单机资源的限制。
  • 分布式存储 利用一致性哈希算法，可以解决缓存等分布式系统的扩容、缩容导致数据大量搬移的难题。

哈希算法还有很多其他的应用，比如网络协议中的 CRC 校验、Git commit id 等等。

哈希表​

关于散列函数的设计，我们要尽可能让散列后的值随机且均匀分布，这样会尽可能地减少散列冲突，即便冲突之后，分配到每个槽内的数据也比较均匀。 除此之外，散列函数的设计也不能太复杂，太复杂就会太耗时间，也会影响散列表的性能。

关于散列冲突解决方法的选择，我对比了开放寻址法和链表法两种方法的优劣和适应的场景。大部分情况下，链表法更加普适。 而且，我们还可以通过将链表法中的链表改造成其他动态查找数据结构，比如红黑树，来避免散列表时间复杂度退化成 O(n)，抵御散列碰撞攻击。 但是，对于小规模数据、装载因子不高的散列表，比较适合用开放寻址法。

对于动态散列表来说，不管我们如何设计散列函数，选择什么样的散列冲突解决方法。随着数据的不断增加，散列表总会出现装载因子过高的情况。这个时候，我们就需要启动动态扩容。

  • 初始大小 HashMap 默认的初始大小是 16，当然这个默认值是可以设置的，如果事先知道大概的数据量有多大，可以通过修改默认初始大小，减少动态扩容的次数，这样会大大提高 HashMap 的性能。
  • 装载因子和动态扩容 最大装载因子默认是 0.75，当 HashMap 中元素个数超过 0.75*capacity（capacity 表示散列表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。
  • 散列冲突解决方法 HashMap 底层采用链表法来解决冲突。即使负载因子和散列函数设计得再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响 HashMap 的性能。
    于是，在 JDK1.8 版本中，为了对 HashMap 做进一步优化，我们引入了红黑树。而当链表长度太长（默认超过 8）时，链表就转换为红黑树。
    我们可以利用红黑树快速增删改查的特点，提高 HashMap 的性能。当红黑树结点个数少于 8 个的时候，又会将红黑树转化为链表。 因为在数据量较小的情况下，红黑树要维护平衡，比起链表来，性能上的优势并不明显。
  • 散列函数 散列函数的设计并不复杂，追求的是简单高效、分布均匀。