0%

哈希表

二十四节气,是干支历中表示自然节律变化以及确立“十二月建”(月令)的特定节令。现行的“二十四节气”采用“定气法”划分,即根据太阳在回归黄道上的位置确定节气;“定气法”把太阳周年运动轨迹划分为24等份,每15°为1等份,每1等份为一个节气,始于立春,终于大寒。

一、哈希表

  1. 哈希表(Hash table,也叫散列表),是根据关键码值(key value)而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

二、哈希函数

  1. 给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希表,函数f(key)为哈希函数。

三、哈希冲突

  1. 哈希算法被计算的数据是无限的,而计算后的结果范围有限,因此总会存在不同的数据经过计算后得到的值相同,这就是哈希冲突。
  2. 解决
    • 开放地址法(再散列法)
      • 线性探查法
      • 平方探查法
      • 双散列函数探查法
    • 链地址法(拉链法)
    • 再哈希法
    • 创建公共溢出区

四、rehash

  1. 当哈希表保存的键值对数量太多或者太少时,需要对哈希表大小进行扩展或者收缩,这就是rehash。