工业级别的散列表有哪些特性呢？
- 快速的查询、插入、删除操作。
- 内存占用合理，不能浪费过多的内存空间。
- 性能稳定，极端情况下，散列表的性能不能退化到无法接受 的情况。
怎么设计呢？ - 合适的散列函数
- 定义装载因子阈值，设计动态扩容策略。
- 选择合适的散列冲突解决办法。
如何设计散列函数
散列函数影响散列表冲突的概率大小，直接决定散列表的性能。设计需要遵循以下几个方法。
- 函数的设计不能太复杂。复杂容易消耗太多的计算时间，间接的影响到性能。
- 生成的值要尽可能随机分布，并且均匀分布。
- 设计方法可以参考直接寻址法，平方取中法，折叠法，随机数法等。
装载因子过大解决
对于静态数据来说根据数据特点，分布设计出完美的，极少冲突的散列函数。
动态数据
动态散列表，数据需要进行动态扩容，将原先的散列表扩容后，装载因子也会进行减小。
扩容后需要进行数据的迁移，这是容易耗费时间的动作。需要重新计算每个数据的存储位置，再进行插入数据到新的散列表中。时间复杂度是O(N)，均摊时间复杂度是O(1);
动态扩容与缩容，我们需要设计好装载因子的阈值，达到阈值之后进行扩容或者缩容。
扩容能帮助提高效率，减少冲突。
缩容减少空间的使用，减少内存的浪费。
阈值的设计需要考虑时间，空间复杂度，执行效率等因素。
避免低效的扩容
扩容需要考虑如果存储的数据量特别大，在G级别以上，那么容易出现就拷贝数据耗费的时间很长，再次插入数据就影响到效率的问题。
一次性的库容的方式就不适合，在此可以采取分而治之的思想。
创建一个新的散列表，然后每次插入新的数据插入到新的散列表中，再把旧表中的数据取出一个放到新的散列表中。不一次性把数据全部迁移，分而治之的迁移。
摘自极客时间
