一 概述

实现哈希集合

  • 哈希函数：能够将集合中任意可能的元素映射到一个固定范围的整数值，并将该元素存储到整数值对应的地址上
  • 冲突处理：由于不同元素可能映射到相同的整数值，因此需要在整数值出现 冲突 时，需要进行冲突处理，由以下三种冲突解决方案：
    • 链地址法：为每一个哈希值维护一个链表，并将具有相同哈希值的元素都放到这一个链表中
    • 开放定址法：每当遇到冲突时，按照一定的策略寻找下一个不冲突的位置，例如：h + 1, h + 2……
    • 再哈希法：当发现哈希冲突时，使用另一个哈希函数产生新的地址
  • 扩容：当哈希元素过多时，冲突的概率越来越大，而在哈希表中查询一个元素的效率也会越来越低，因此需要开辟一块更大的空间，来缓解哈希表中发生的冲突， 掌握实现

二 扩容实现