数据结构之散列表_数据结构 散列表

一、散列表的概念

        散列表(Hash Table)又名哈希表/Hash表，是根据键（Key）直接访问在内存存储位置值（Value）的数据结构，它是由数组演化而来的，利用了数组支持按照下标进行随机访问数据的特性。

二、散列函数

        假设有100个人参加马拉松，不采用1-100的自然数对选手进行编号，编号有一定的规则比如：2023ZHBJ001，其中2023代表年份，ZH代表中国，BJ代表北京，001代表原来的编号，那此时的编号2023ZHBJ001不能直接作为数组的下标，此时应该如何实现呢？

将键(key)映射为数组下标的函数叫做散列函数。可以表示为：hashValue = hash(key)。

散列函数的基本要求：

 1. 散列函数计算得到的散列值必须是大于等于0的正整数，因为hashValue需要作为数组的下标。

 2. 如果key1==key2，那么经过hash后得到的哈希值也必相同即：hash(key1) == hash(key2）。     3. 如果key1 != key2，那么经过hash后得到的哈希值也必不相同即：hash(key1) != hash(key2)。

三、散列冲突

        实际的情况下想找一个散列函数能够做到对于不同的key计算得到的散列值都不同几乎是不可能的，即便像著名的MD5,SHA等哈希算法也无法避免这一情况，这就是散列冲突(或者哈希冲突，哈希碰撞，就是指多个key映射到同一个数组下标位置)。

那应该怎么解决这个问题呢？继续向下看。

四、拉链法（链表法）

1.定义

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

2.时间复杂度

（1）插入操作，通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，插入的时间复杂度是 O(1)。

  (2）当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除：

        1. 平均情况下基于链表法解决冲突时查询的时间复杂度是O(1)。

        2. 散列表可能会退化为链表,查询的时间复杂度就从 O(1) 退化为 O(n)。

        3. 将链表法中的链表改造为其他高效的动态数据结构，比如红黑树，查询的时间复杂度是 O(logn)。

3.ddos攻击

        将链表法中的链表改造红黑树还有一个非常重要的原因，可以防止ddos攻击。

        DDOS 攻击: 分布式拒绝服务攻击(英文意思是Distributed Denial of Service，简称DDOS， 指处于不同位置的多个攻击者同时向一个或数个目标发动攻击，或者一个攻击者控制了位于不同位置的多台机器并利用这些机器对受害者同时实施攻击。由于攻击的发出点是分布在不同地方的，这类攻击称为分布式拒绝服务攻击，其中的攻击者可以有多个。