散列表的定义、操作特性和典型应用是什么？
散列表的定义、操作特性和典型应用
散列表借助的是数组的定义、操作特性和典型应用根据下标随机访问时复杂度为 O(1) 的特性。依据散列函数把元素的 key 映射为下标，然后将数据存储在数组中对应下标的位置。当我们依据 key 查询元素时，我们使用同样的散列函数，将 key 转化为数组下标，以此查找数据 散列函数 hash(key)，key 表示元素的键值，hash(key)的值表示经过散列函数计算得到的散列值。
- 散列函数计算得到的散列值是一个非负整数
- 如果 key1 = key2，则 hash(key1) = hash(key2)
- 如果 key1 ! key2，则 hash(key1) ! hash(key2) 散列冲突 几乎没有散列函数可以做到，key 不同、hash(key) 也不同。这种情况被称为散列冲突，我们需要几种解决方案来处理散列冲突的问题。
- 开放寻址法：如果出现课散列冲突，就重新探测一个空闲位置，将其插入。
- 线性探测：某个数据经过散列函数散列后，存储位置被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。
- 链表的定义、操作特性和典型应用法：每个“槽(slot)”都会对应一条链表，我们把所有散列值相同的元素，都放到相同槽位对应的链表的定义、操作特性和典型应用中。 装载因子 为了保证散列表的操作效率，降低散列冲突的几率，我们一般会尽可能保证散列表中有一定比例的空闲槽位。这个用来表示散列表中还有多少空位的的指标被称为装载因子(load factor)。装载因子越大，说明空闲位置越少，冲突越多，散列表的性能就会下降。
散列表的装载因子 = 填入表中的元素个数 / 散列表的长度
散列表的设计
- 散列函数的设计不能太复杂，避免消耗过多的计算时间
- 散列函数生成的值要尽可能随机分布，这样才能避免或者最小化散列冲突，即使出现冲突，散列到每个槽里的数据也会比较平均，不会出现某个槽内数据特别多的情况