集合

什么是散列表？

❒ 散列表(hash table)
✔ 散列表(hash table)又名哈希表/hash表。
✔ 根据键(key)直接访问在内存存储位置值(value)的数据结构。
✔ 由数组演化而来的，利用了数组支持按照下标进行随机访问数据的特性。

❒ 散列函数
✔ 将键(key)映射为数组下标的函数叫做散列函数。可以表示为：hashValue = hash(key)。
✔ 散列函数计算得到的散列值必须是大于等于 0 的正整数，因为hashValue需要作为数组的下标。
✔ 如果key1 == key2，那么经过hash后得到的哈希值也必相同即：hash(key1) == hash(key2)。
✔ 如果key1 != key2，那么经过hash后得到的哈希值也必不相同即：hash(key1)  != hash(key2)。

❒ 散列冲突
✔ 散列函数对于不同的key计算得到的散列值相同，这就是散列冲突(或者哈希冲突，哈希碰撞，就是指多个key映射到同一个数组下标位置)

❒ 散列冲突-链表法(拉链)
✔ 在散列表中，数组的每个下标位置我们可以称之为桶(bucket)或者槽(slot)，每个桶(槽)会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

❒ 散列冲突-链表法(拉链)-时间复杂度
✔  插入操作，通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，插入的时间复杂度是O(1)。
✔  当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除。
✔ 平均情况下基于链表法解决冲突时查询的时间复杂度是O(1)。
✔ 散列表可能会退化为链表,查询的时间复杂度就从0(1)退化为 O(n)。
✔ 将链表法中的链表改造为其他高效的动态数据结构，比如红黑树，查询的时间复杂度是0(log n)。

❒ 什么是散列表?
✔ 散列表(hash table)又名哈希表/hash表。
✔ 根据键(key)直接访问在内存存储位置值(value)的数据结构。
✔ 由数组演化而来的，利用了数组支持按照下标进行随机访问数据。

❒ 散列冲突
✔ 散列冲突又称哈希冲突，哈希碰撞。
✔ 指多个key映射到同一个数组下标位置。

❒ 散列冲突-链表法(拉链)
✔ 数组的每个下标位置称之为桶(bucket)或者槽(slot)。
✔ 每个桶(槽)会对应一条链表。
✔ hash冲突后的元素都放到相同槽位对应的链表中或红黑树中。