4 扩容

• 没有频繁插入和删除的静态数据集合，即使实习生也能轻松根据数据特点，设计出优秀的hash函数
• 而动态hash表，数据频繁变动，无法预估数据个数，所以无法预申请一个足够的hash表。随数据越多，装载因子就会慢慢变大。当装载因子大到一定程度后，哈希冲突就会令程序窒息，此时资深的程序员们该咋办呢？

针对hash表，当 loadFactor 过大，可进行动态扩容，新申请更大的hash表，将数据迁移至新hash表。

假设每次扩容，申请一个原来hash表两倍size的。若原hash表装载因子0.8，则扩容后的新hash表装载因子就降为原来的一半0.4了。

但hash表的扩容，数据搬移操作要复杂很多。因为哈希表的大小变了，数据的存储位置也变了，需通过hash函数重新计算每个数据的存储位置。

原来hash表的21存储在0位，迁移新hash表后存储在7位。

动态扩容的散列表，插入操作的时间复杂度是多少呢？

插入一个数据：

最好无需扩容，时间复杂度O(1)

最坏情况，hash表loadFactor过高，开启扩容新申请内存空间，重新计算哈希位置并迁移数据，时间复杂度O(n)。用摊还分析法，均摊情况下，时间复杂度接近最好情况，就是O(1)。

动态散列表，随着数据的删除，散列表中的数据会越来越少，空闲空间会越来越多。

如果对空间消耗非常敏感，可以在装载因子小于某个值之后，启动动态缩容。

如果更在意执行效率，能够容忍多消耗一点内存空间，就不用费劲缩容。

避免低效扩容

大部分情况下，动态扩容的hash表插入一个数据都很快，但特殊情况下，当装载因子达阈值，需先扩容，再插数据。这时，插入数据就会变得很慢！

若hash表当前大小为1G，想扩容为原来2倍，就需对1G数据重新计算哈希值并从原hash表搬移到新表，听着都耗时！

所以这时，“一次性”扩容机制就不合适了。

为避免一次性扩容耗时过多，可将扩容操作穿插在插入操作的过程中分批完成。当装载因子达阈值后，只申请新空间，但并不将老数据搬移到新hash表。

当有新数据插入，将新数据插入新hash表中，并从老原hash表拿出一个数据放入新hash表。

每次插入一个数据到散列表，重复上面过程。

经过多次插入操作之后，原hash表的数据就一点点都迁移至新hash表。这就不会一次性数据搬移，插入操作就都变得很快了。

这期间的查询操作怎么做？

为兼容新、老hash表数据，先查新hash表，没找到再去原hash表查找。

通过这样的均摊，将一次性扩容代价，均摊到多次插入操作，解决一次性扩容耗时过多问题。这时任何情况下，插入一个数据的时间复杂度都是O(1)。

应用

强大的 HashMap

1.初始大小

HashMap默认的初始大小是16，当然这个默认值是可以设置的，如果事先知道大概的数据量有多大，可以通过修改默认初始大小，减少动态扩容的次数，这样会大大提高HashMap的性能。

2.装载因子和动态扩容

最大装载因子默认是0.75，当HashMap中元素个数超过0.75*capacity（capacity表示散列表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。

3.散列冲突解决方法

HashMap底层采用链表法来解决冲突。即使负载因子和散列函数设计得再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。

于是，在JDK1.8版本中，为了对HashMap做进一步优化，我们引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树。我们可以利用红黑树快速增删改查的特点，提高HashMap的性能。当红黑树结点个数少于8个的时候，又会将红黑树转化为链表。因为在数据量较小的情况下，红黑树要维护平衡，比起链表来，性能上的优势并不明显。

4.散列函数

散列函数的设计并不复杂，追求的是简单高效、分布均匀。我把它摘抄出来，你可以看看。

int hash(Object key) {
    int h = key.hashCode()；
    return (h ^ (h >>> 16)) & (capitity -1); //capicity表示散列表的大小
}

其中，hashCode()返回的是Java对象的hash code。比如String类型的对象的hashCode()就是下面这样：

public int hashCode() {
  int var1 = this.hash;
  if(var1 == 0 && this.value.length > 0) {
    char[] var2 = this.value;
    for(int var3 = 0; var3 < this.value.length; ++var3) {
      var1 = 31 * var1 + var2[var3];
    }
    this.hash = var1;
  }
  return var1;
}

单词拼写检查功能是如何实现的？

常用英文单词20万个，假设单词平均长度10个字母，平均一个单词占用10字节，那20万英文单词大约占2MB存储空间，这完全可以放在内存。所以我们可以用散列表来存储整个英文单词词典。

当用户输入某个英文单词时，拿用户输入的单词去散列表中查找：

• 查到，则说明拼写正确
• 没有查到，则说明拼写可能有误，给予提示

这就能轻松实现快速判断是否存在拼写错误。