【数据结构】散列表(哈希表)hash table

Hash table                                                                   


在计算机中,散列表 是 一种实现了关联数组 抽象数据类型的数据结构,这种数据结构可以映射 键(key) 和 值(value).

补充:

关联数组:在计算机科学中,一个关联数组(associative array),映射(map),符号表(symbol table),或者是字典(dictionary)是由键值对集合组成的 抽象数据类型 的 一种;

抽象数据类型:在计算机科学中,一个抽象数据类型(abstract data type ADT)是 具有类似行为的特定类别的数据类型 的数学模型;

散列表 通过 一个关于键值的 散列函数 ,将 所需查询的数据映射到 表中的一个位置 来访问记录;

在理想状态下,散列函数将 每个键(key) 分配给 唯一的 bucket,但是大多数 散列表 的 散列函数的不完善性,会导致 哈希碰撞(collision),即哈希函数 为不同的 key 生成了相同的 索引(index);

Hashing                                                                                  


散列法(hashing)的思想是 在 桶数组(array of buckets)中 分配  entry(键值对)。给定一个 键(key),该算法计算出一个 索引,该索引代表了 entry 的 地址。

index = f(key, array_size)

通常这是分两步完成:

hash = hashfunc(key)
index = hash % array_size

在上面的方法中,hash 值 与数组 大小无关,然后利用 他 和  数组 大小 取模运算 得到 索引值(0 到 array_size -1  之间的一个数字);

一个好的 哈希函数  和 算法实现 对于 散列表的性能 有很大的提升,但是通常也很难做到。

load factor                                                                                

加载因子

load factor = n / k

n:填入表中的元素个数
k:散列表的长度

散列表长度固定的前提下,加载因子 越大,填入表中的元素越多,发生冲突的可能性越大,效率也就越慢;


Collision resolution                                                                         

哈希冲突时不可避免的,以下列出了常见的 哈希冲突解决策略,所有的解决方法都需要 将 键 存储在 表中。

  • 开放地址法 (open addressing,也叫做 closed hashing):所有的 条目(entry,即键值对)记录 保存在 桶数组(bucket array)中。当需要插入一个新的 键值对时,首先从 hash对应的位置开始检查 buckets,直到发现一个没有被占用的 位置。
  • 分离链表法(separate chain):每个 bucket 是 独立的;是具有相同索引的条目列表。哈希表的操作时间 等于 查找t(桶所在位置的时间 加上  列表的操作时间 。(java 中 HashMap 使用该方法,数组的每个位置代表一个桶,每个位置上存储了链接列表)
相关文章
相关标签/搜索