❒ 散列表(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计算得到的散列值都不同几乎是不可能的，即便像著名的MD5,SHA等哈希算法也无法避免这一情况，这就是散列冲突(或者哈希冲突，哈希碰撞，就是指多个key映射到同一个数组下标位置)
❒ 散列冲突-链表法(拉链)
在散列表中，数组的每个下标位置我们可以称之为桶(bucket)或者槽(slot)，每个桶(槽)会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。
❒ 散列冲突-链表法(拉链)-时间复杂度
(1)插入操作，通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，插入的时间复杂度是O(1)
(2)当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除
✔ 平均情况下基于链表法解决冲突时查询的时间复杂度是O(1)
✔ 散列表可能会退化为链表,查询的时间复杂度就从0(1)退化为 O(n)
✔ 将链表法中的链表改造为其他高效的动态数据结构，比如红黑树，查询的时间复杂度是0(logn)