散列

散列表的实现通常叫散列,散列是一种用于以常数平均时间执行插入,删除,查找的技术。

1.一般想法

  • 理想的散列结构是一个包含有一些项的具有固定大小的数组。
  • 这些项由一些关键字和数据域组成。

假设一个表大小为size,那么每个关键字被映射到从0到size-1这个范围中的某个数,并放着适当的单元中,这个映射就叫做散列函数

理想情况下,他应该计算起来简单,并保证任何两个不同的关键字映射到不同的单元。。。。不过,这是不可能的,-因为单元的数目是有限的,而关键字实际上是用不完的。

  • 因此,要寻找一个散列函数,这个函数要能在单元间均匀地分配关键字。

所以关键就是散列函数,以及将两个关键字散列到同一个值的时候该怎么解决这个冲突。

2.散列函数

散列函数主要是将一个key通过计算生成一个散列值,key是不能重复的,但生层的散列值可能会一样,散列函数要尽量保证了生成的散列值不同且在范围内均匀分布。

  • 如果key是整数,那么一般的方法是直接返回这个key除以tableSize的余数

    因此tableSize最好用素数,这样能避免出现大量的重复结果。

    1
    2
    3
    public static int hashCode(int key, int tableSize) {
    return key % tableSize;
    }
  • 通常关键字key是字符串,这时有几个散列函数的选择:

    1. 把字符串中ASCII值加起来:

      1
      2
      3
      4
      5
      6
      7
      public static int hashCode1(String key, int tableSize) {
      int hashCode = 0;
      for (int i = 0; i < key.length(); i++) {
      hashCode += key.charAt(i);
      }
      return hashCode % tableSize;
      }

      假设表大小是10007,是素数,并设所有关键字最多8个字符,ASCII字符的值最大为127,那么散列值只能在0和1017(128*8)之间,明显分配不均

    2. 假设至少有三个字符

      1
      2
      3
      4
      5
      public static int hashCode2(String key, int tableSize) {
      int hashCode = 0;
      hashCode = key.charAt(0) + 27 * key.charAt(1) + 27 * 27 * key.charAt(2);
      return hashCode % tableSize;
      }
    3. 涉及到key中的所有字符,一般分布的很好。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      public static int hashCode3(String key, int tableSize) {
      int hashCode = 0;
      for (int i = 0; i < key.length(); i++) {
      hashCode = 37*hashCode+key.charAt(i);
      }
      hashCode%=tableSize;
      if (hashCode<0){
      hashCode+=tableSize;
      }
      return hashCode;
      }

    String类中的hashCode

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
    char val[] = value;
    for (int i = 0; i < value.length; i++) {
    h = 31 * h + val[i];
    }
    hash = h;
    }
    return h;
    }

剩下的就是解决冲突的问题了。

3.解决冲突

1.分离链接法

将散列到同一个值的所有元素保存在一个表中。

使用下面的散列函数,并让表大小为10 ,不是素数,所以很容易产生重复的散列值:

1
2
3
public static int hashCode(int key) {
return key % 10;
}

hashCode(26) =6

插入 12,32,44,24,76,34,49,90:

要执行一次查找,先用散列函数确定所在的链表,然后遍历这个链表。

要执行一次插入,先用散列函数确定要插入的链表,然后查到这个链表的前端。因为新数据经常会被访问。

填装因子

  • 填装因子=散列表总元素的个数/散列表的大小。

    可以理解为平均一个位置会有多少元素。当填装因子为1时,平均一个位置上一个元素。

  • 在使用分离链接法的散列表中,执行一次查找锁需要的时间=计算散列函数值的时间+遍历链表的时间。,所以链表越短,速度越快。

    使用分离连接法时,一般要使填装因子接近1,也就是尽量一个位置上只有一个元素。,当填装因子大于1时,就要通过扩大散列表的大小来降低填装因子。

  • 对于不适用分离连接法的散列表来说,填装因子应该低于0.5。

2.开放定址法

分离链接法的缺点是使用了链表,个新单元分配地址需要时间,而且需要第二种数据机构的实现。

另一中不需要链表的解决冲突的方法就是尝试寻找另一个空的位置来存放元素。

所以不适用分离连接法的散列表的填装因子要小,应该低于0.5.

这种表叫探测散列表。

  • 一般当h_1(x)地址上没空时,选h_2(x),h_2(x)地址上也有值时,选h_3(x),。。。

    这一系列函数的关系是
    $$
    h_i(x) =(hash(x)+f(i)) \mod tableSize
    $$
    其中的f(i)就是解决冲突的方法。下面有三种:

2.1 线性探测法

f(i)是线性函数,
$$
f(i) = i
$$
f(0) = 0 ;

这相当于逐个探测单元(到头时可以回绕),直到查找到一个空的单元。

比如还是用下面的散列函数 插入插入 12,32,44,24,76,34,49,90:

1
2
3
public static int hashCode(int key) {
return key % 10;
}
位置 空表 插入12 插入32 插入44 插入24 插入76 插入34 插入49 插入90
0 90
1
2 12 12 12 12 12 12 12 12
3 32 32 32 32 32 32 32
4 44 44 44 44 44 44
5 24 24 24 24 24
6 76 76 76 76
7 34 34 34
8
9 49 49
  1. 在插入12的时候散列表式空的,通过散列函数计算得到的位置是2,位置2上没有值,就把12放在位置2上

  2. 插入第二个数32的时候,散列函数的结果也是2,但是位置2上已经有12了,所以往下进行探测,下一个位置的计算方法是:
    $$
    hash(32) = 2 \
    第一个位置: h_0(32) = (hash(32)+f(0)) \mod 10 =2 \
    但是位置2上已经被12占用了,所以就要寻找下一个位置:\
    第二个位置:h_1(32)=(hash(32)+f(1)) \mod 10 = 3\
    位置3上刚好有空,就把32放在位置3上了,完成插入。
    $$

可以想象,当这个散列表的空位不多的时候,插入一个数据经常要探测很多个位置才能找到一个空位,所以这个散列表要求填装因子第一次点,低于0.5的时候,插入和查询是探测的次数会大大减少。

2.2 平方探测法

f(i)是二次函数,
$$
f(i) = i^2
$$

$$
h_i(x) =(hash(x)+f(i)) \mod tableSize
$$

这个方法有个缺陷是,第一次散列的位置相同时,那么他们接下来的探测位置也会相同,后面那个会把前面那个谈错过的位置再探测一遍。

使用双散列可以解决这个,不过要付出计算一个附加的散列函数的代价。

  • 使用平方探测且表的大小是素数时,那么当表至少有一半是空的时候,总能插入一个新元素。

2.3 双散列法

双散列流行的公式是:
$$
f(i) = i·hash_2(x)
$$
其中hash_2(x)是另外一个散列函数,在第一册散列得到位置后,如果这个位置不是空的,那么就移动到1*hash__2(x)位置,这个位置再被占用就移动到2*hash__2(x)位置。

这里第二个散列函数hash_2(x)就很重要了,如果这个函数得到的结果为0,那么f(i)的结果就为0,那么探测到位置就不会变,这是灾难。所以这个函数的计算结果一定不能为0 。

可以使用下面的:
$$
hash_2(x) = R -(x\mod R)\
R为小于tableSize的素数。
$$
使用双散列也要保证表的大小是素数,不然可能吧备选单元提前用完。

3.再散列

当填装因子达到一定的值的时候,如使用分离链接法达到1,使用开放地址法达到0.5,需要扩大散列表。

一种解决办法是:建立一个两倍大的表,并使用一个新的散列函数,扫描原始表,计算每个未删除的元素的新的散列值,并插入到新表中。

假设一个散列表大小为7,解决冲突方法是分离链接法。,散列函数是
$$
hash(x) = x\mod 7
$$
向里面插入数据 13,15,24,6得到下面的表:

然后在插入个23:

这是觉得表有点满了,将表扩大2倍。

因为要让表的大小是素数,所以选择别7的二倍14还大的最接近的素数,17,新表的大小为17.

将散列函数变为:
$$
hash(x) = x\mod 17
$$
插入到新表变成:

这个操作就叫再散列。虽然每次扩容的开销很大,但因为每次扩容都直接把容量翻倍了,所以在之后的插入中花费基本上是一个常数开销。

实现再散列有多个方法:

  • 表满一半就开始再散列
  • 插入失败开始再散列
  • 填装因子达到某一个值是开始再散列

4.标准库中的散列表

HashMap和HashSet通常使用分离链接散列实现的

String的hashCode有一个重要优化,就是把散列值存储在String对象中,该值初始值为0 ,只用计算一次。

可以避免昂贵的重新计算,这个技巧叫内存散列代码,是一种空间交换时间。

之所以String可以这样,是因为String类是不可变的。