数据结构与算法(26): 散列

发表于   |   分类于

散列是一种用于以常数平均时间执行插入、删除和查找的技术。

散列表(Hash Table)就是一种以键-值存储数据的结构。

使用哈希查找有两个步骤:
  1. 使用散列函数将被查找的键转换为存储单元的索引。在理想的情况下，不同的键会被转换为不同的索引值，但是在有些情况下多个键被散列到同一个索引值，所以第二个步骤就是处理冲突。
  2. 处理散列碰撞冲突。拉链法（分离链接法）和线性探测法（开放定址法）。

散列函数

  散列函数将键映射成存储单元的索引。如果我们有一个保存0-M数组，那么我们就需要一个能够将任意键转换为该数组范围内的索引（0~M-1）的哈希函数。散列函数需要易于计算并且能够均匀分布所有键。

  1. 整数
    获取整数的哈希值一般使用除留余数法。即大小为素数M的数组，对于任意整数K，计算K除以M的余数。

    表的大小M取素数，使得可以充分利用键中所包含的信息，从而均匀的散列哈希值。
    例如：如果键是十进制而M为$10^k$，使用除留余数法则只能利用键的后k位。

  2. 字符串
    将字符串作为键的时候，也可以将它作为一个大的整数，采用保留除余法。可以将组成字符串的每一个字符取值然后进行散列。

    1
    2
    3
    4
    5
    6
    7
    public int hashCode(String s){
    	int hash = 0;
        for(int i = 0; i < s.length(); i++{
        	hash = s[i] + 31 * hash;
        }
        return hash;
    }

哈希冲突

拉链法

拉链法：将大小为M的数组的每一个元素指向一个条链表，链表中的每一个节点都存储散列值为该索引的键值对。

该方法的基本思想就是选择足够大的M，使得所有的链表都尽可能的短小，以保证查找的效率。

线性探测法

线性探测法：使用大小为M的数组来保存N个键值对，其中M>N，我们需要使用数组中的空位解决碰撞冲突。

开放寻址法中最简单的是线性探测法：当碰撞发生时即一个键的散列值被另外一个键占用时，直接检查散列表中的下一个位置即将索引值加1，这样的线性探测会出现三种结果：

  • 命中，该位置的键和被查找的键相同；
  • 未命中，键为空；
  • 继续查找，该位置和键被查找的键不同。