纯数据结构Java实现(11/11)(散列)

实现 Hash表 的难度远低于设计一个 Hash函数

主要有两个重点,Hash函数的设计冲突处理

Hash函数

Hash基本概述

我有很长一段时间内搞不清楚网络安全中的指纹摘要函数与哈希存储结构的Hash运算。

简而言之,一个是 Hash Function,另一个只是 HashTable Function。

  • HashTable Function 是要直接拿到索引进行数据存储的,即如果 Hash Function 计算出的是 -42,显然 HashTable Function就要进行相应的包装,转换为具体的索引才能进行存储
  • Hash函数拿到Hash值,至于如果转具体索引,这就交给Hash表结构,比如一般都会取模桶(bucket)的数量

但显然,两者都具备将原输入转换为一个唯一值,即原值(key)对应一个unique值。

  • key 的类型不同,取值范围的复杂性,导致了设计一个 hash 冲突少的 hash 函数的困难
  • hash值冲突外,一般还对 分布是否均匀 有要求

在 hash表结构中,可以简单的理解 Hash函数就是 键转换到索引 的函数。

同时也具备一些基本的特征(基本论述和密码,网络安全中加密,摘要部分类似):

基本特性

Hash函数设计

根据不同的 key 类型设计不同的 Hash 函数

要设计好一个 Hash函数,一般需要对 key 进行研究,但一般而言,有一些基本的方法,什么平方法,乘法,取模法。但无论怎么样,都会对 key 的信息进行摘要研究。

以取模为例,一般会都会取模素数,这里有一个参考:

数据规模-素数

(某个数据规模范围内,其实还是有不同的选择的)

浮点型 当做整型处理(取模)。

字符串 也可以转换为证型去处理 (转换为一个大整数,然后取模素数):

'198' = 1 * 10 ^2 + 9 * 10^1 + 8 * 10^0

'xyz' = x * 26^2 + y * 26^1 + z * 26^0

编程的时候,比如在循环时可能需要做一下等价变形:

等价变形

内部小括号内数字太大,可能存在整型溢出,可以再次变形:

避免整型溢出

(这里的变形需要 数论 相关的知识背景)

//上面的最终变形,代码实现如下:
int hash = 0; //第一次就不用 %M 了,因为是 0
for(int i = 0; i < s.length(); i++) {
      hash = (hash*B + s.charAt(i)) % M; //每次计算都要取模
}

复合类型:

拆分/合并字段为字符串,然后再转换为整型,例如:

复合类型的处理

Java中hashCode方法

hashCode 方法只负责将 key 生成哈希值

Java 中的基本类型,先转换为包装类型,然后可以直接取包装类实现的 hashCode()。

  • 整型,直接返回本身 (负数则返回负数)
  • 浮点数,转换成整型 (一般返回大整数)

还是写代码验证一下吧,口说无凭:

public static void main(String[] args) {
    int a = 1;
    System.out.println(((Integer)a).hashCode()); //1

    int b = -2;
    System.out.println(((Integer)b).hashCode()); // -1

    double c = 3.12415;
    System.out.println(((Double)c).hashCode()); // 451321186

    String d = "mine";
    System.out.println(d.hashCode());//3351635
}

对于复合类型,一般都要覆盖 Object 类的 hashCode 方法,写法也比较固定:

  • 有的人喜欢拿出其中的部分字段作为 hashCode 的依据,也行
  • hashCode 重写时,一般也要重写 equals 方法
  • 如果不覆盖,默认的是按照对象的存储地址计算的
    • 此时即便两个对象的字段全部相同,得到结果也不同
public class Student {

    int grade;
    int cls;
    String firstName;
    String lastName;

    Student(int grade, int cls, String firstName, String lastName){
        this.grade = grade;
        this.cls = cls;
        this.firstName = firstName;
        this.lastName = lastName;
    }

    @Override
    public int hashCode(){
        //做法还是转换为大整数
        //所有字段都参与
        //上一层运算的结果一般要 *B 之后再和本次字段 hash值 求和
        int B = 31;
        int hash = 0;
        hash = hash * B + ((Integer)grade).hashCode();
        hash = hash * B + ((Integer)cls).hashCode();
        hash = hash * B + firstName.toLowerCase().hashCode();
        hash = hash * B + lastName.toLowerCase().hashCode();
        return hash;
    }

    @Override
    public boolean equals(Object o){
        if(this == o)
            return true;

        if(o == null)
            return false;

        if(getClass() != o.getClass())
            return false;

        Student another = (Student)o;
        return this.grade == another.grade &&
                this.cls == another.cls &&
                this.firstName.toLowerCase().equals(another.firstName.toLowerCase()) &&
                this.lastName.toLowerCase().equals(another.lastName.toLowerCase());
    }
}

上面的计算,即便有大整数溢出,根据Java溢出处理的机制,也是能得到大整数的。

Hash冲突

可以这么说,Hash结构之所以有多种实现,就是因为对Hash冲突的解决办法不同

  • Hash函数也很难保证每一个键转换得到的索引不同 (不同键产生同样的value时就出现了冲突)

Hash函数设计的好,那么冲突就会少,换言之,key 的存储越均匀。

Hash实现

一种典型的 空间换时间 的结构,实现的时候则考虑时间空间的平衡。

假设能开辟无限空间,借助索引的随机访问性能,此时所有的操作都是 O(1)。

但存储 Hash 空间的表比较小(可以理解为桶少),那么甚至可能会退化到 O(n)。

封闭-链地址

Seperate Chaining 方法,即每个桶(bucket)还可以拓展多个链(冲突的都放在后面的查找表中)。

形状大家见的比较多,但如何把 hash值转到 index 有一些技巧

链地址发

后面的查找表可以是链结构,顺序结构,当然也可以是树结构,比如每个元素都是 TreeMap:

TreeMap数组结构

(其他结构作为子结构也未尝不可,Java8的实现是在查找表太长的时候,会自动转换为TreeMap,即红黑树结构)

实现也简单,就是内部封装一个 LinkedList/TreeMap 的数组即可。

  • 放入查找表的元素都要实现 hashCode方法 (显然 Object 类已经帮您默认实现了)

这里处理 Hash表 的 Hash函数有一些特殊(注意取正数以及数组长度为素数)

//Hashtable的 hash函数 (要直接拿到存储索引的,而不是只求出hash值)
private int hash(K key) {
    // 0x7fffffff 相当于去掉整型的符号位
    //因为 java 本身实现的 hashCode 本身可能为负值(这里运算后最高位一定是0,即正数)
    //不用与运算,用 Math.abs 也是可以的,但效率不高
    return (key.hashCode() & 0x7fffffff) % M;
}

此时基本实现框架如下:

package hash;

import java.util.TreeMap;

public class HashTable<K, V> {
    private TreeMap<K, V>[] table;
    private int M; //一个素数,其实也是 buckets 的目录(数组长度)
    private int size; //元素总个数

    //指定数组长度的构造器
    public HashTable(int M) {
        this.M = M;
        size = 0;
        table = new TreeMap[M]; //数组长度也是 M
        //数组的元素也要初始化
        for(int i = 0; i < M; i++) {
            table[i] = new TreeMap<>();
        }
    }

    //默认数组长度 97,当然也可以是其他素数
    public HashTable() {
        this(97);
    }

    //Hashtable的 hash函数 (要直接拿到存储索引的,而不是只求出hash值)
    private int hash(K key) {
        // 0x7fffffff 相当于去掉整型的符号位
        //因为 java 本身实现的 hashCode 本身可能为负值(这里运算后最高位一定是0,即正数)
        //不用与运算,用 Math.abs 也是可以的,但效率不高
        return (key.hashCode() & 0x7fffffff) % M;
    }

    public int getSize() {
        return size;
    }

    public static void main(String[] args) {

    }
}

下面就是在 TreeMap 中的增删改查了 (注意维护size)。

  • 先找到对应 bucket 的 map,然后再 map 中操作

增加:

public void add(K key, V value) {
    //先要看一下是否存在 (不存在才存储;否则是修改)
    TreeMap<K, V> map = table[hash(key)];
    map.put(key, value);
    if(!map.containsKey(key)) {
        //新添加
        size++;
    }
}

删除:

public V remove(K key) {
    TreeMap<K, V> map = table[hash(key)];

    V ret = null;
    //在相应的 map 中查找
    if(map.containsKey(key)) {
        ret = map.remove(key);
        //删除之后要维护 size
        size--;
    }
    return ret;
}

更新:

public void set(K key, V value) {
    TreeMap<K, V> map = table[hash(key)];
    if(!map.containsKey(key)) {
        throw new IllegalArgumentException(key + "不存在")
    }
    map.put(key, value);
}

查询:

//查询
public boolean contains(K key) {
    //TreeMap<K, V> map = table[hash(key)];
    return table[hash(key)].containsKey(key);
}

public V get(K key) {
  return table[hash(key)].get(key);
}

简单测试:

public static void main(String[] args) {
    HashTable<String, Integer> hashTable = new HashTable<>();
    hashTable.add("nihao", 1);
    hashTable.add("hello", 2);

    System.out.println(hashTable.contains("nihao")); //true
    hashTable.set("hello", 3);
    System.out.println(hashTable.get("hello")); //3
}

时间复杂度分析

其实很好分析,关键是看后面查找表的长度。(因为桶默认是常量级别,即O(1))

有 M 个bucket,一共存储了 N 个元素,那么每个 Bucket 的查找表长度就是 N/M。

所以,如果查找表的实现:

  • 线性表,那么复杂度就是 O(N/M)
  • 平衡树,那么复杂度就是 O(log(N/M))

注意 N/M 是分布平均的情况,即通常而言(如果 hash函数设计的不好,即分布不平均,那就惨了)。

如果要 O(1) 的时间复杂度,那么就必须使用动态数组。(都是 O(1) 的随机存储拿到值)

  • 即全部都是存在数组中(查找表的第一个位置),也就是相当于直接从数组中拿 (数组要大)

改进的措施,动态扩充bucket:

  • N/M >= 某个值,说明某个查找表太长了(比如某个地址的查找表存储很长),扩充 bucket
  • N/M < 某个值,缩容

(当然像 Java8 那样改变查找表的结构,即从 linkedlist 到 treemap 也算一种补救,但本质不是O(1))

添加动态扩容机制

这纯碎就是拿空间换时间的一种措施,不管说的多好听,多高级

首先,确保这个机制的执行,需要确定 factor 因子 (查找表接多少元素扩容缩容):

//扩容因子
private static final int up_factor = 10; //表示 10 倍于 M,即数组长度
private static final int low_factor = 2;
private static final int init_capacity = 7; //相当于初始的 M (用户不传入 M 的构造器)

//相应的修改默认构造器
public HashTable() {
  this(init_capacity);
}

此时 add 和 remove 的逻辑都要进行修改:

//添加
public void add(K key, V value) {
    //先要看一下是否存在 (不存在才存储;否则是修改)
    TreeMap<K, V> map = table[hash(key)];
    map.put(key, value);
    if(!map.containsKey(key)) {
        //新添加
        size++;

        //添加完毕之后,要检查是否需要扩容
        if(size >= up_factor * M) {
            resize(2*M);
        }
    }
}

//删除
public V remove(K key) {
    TreeMap<K, V> map = table[hash(key)];

    V ret = null;
    //在相应的 map 中查找
    if(map.containsKey(key)) {
        ret = map.remove(key);
        //删除之后要维护 size
        size--;
        // 可以写 M/2 >0 或者 M/2 !=0 都行
        if(size < low_factor * M && M/2 > init_capacity) {
            resize(M / 2);
        }
    }
    return ret;
}

resize 就是重新分配(TreeMap)数组,然后遍历元素,放入新 hash table。

  • 特别注意一下这里的 M,即 bucket 的大小个数已经变化了(意思是 hash 结果也变了)
private void resize(int newCapacity) {
    //创建一个新的数组
    TreeMap<K, V>[] newHashTable = new TreeMap[newCapacity];
    //初始化每个 bucket 的查找表(TreeMap)
    for(int i = 0; i < newCapacity; i++) {
        newHashTable[i] = new TreeMap<>();
    }

    //然后遍历旧的数组,放入新的数组
    int oldCapacity = M;
    this.M = newCapacity;
    for(int i = 0; i < oldCapacity; i++) {
        //拿到当前的查找表
        TreeMap<K, V> map = table[i];
        TreeMap<K, V> newMap;
        //遍历这个查找表,放入新容器
        for(K key: map.keySet()) {
            newMap = newHashTable[hash(key)];
            newMap.put(key, map.get(key)); //放入的新 map
        }
    }
    this.table = newHashTable;
}

此外,这类的扩容一般会是选择一个序列的值,而不是翻倍

上面是 M -> 2*M,但实际上,此时 bucket 就不是一个素数了,势必导致 hash 函数结果冲突增多。

所以即便扩容, M 也应该在一个序列中选取,比如 [7, 53, 87, 193, 289] 等。

//扩容的可选序列
private final int[] capacity
        = {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
        49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
        12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};

此时每次扩容的时候只需要 index + 1即可。(开始的时候 init_capacity 取值为 0,表示索引为 0)

相应的增删的写法,以及 index 越界的判断都要重新书写:

private static int init_capacity_index = 0; //素数表中选择容量

//构造器 (数组的初始长度从 capacity 数组中查找)
public AdvanceHashTable() {
    this.M = capacity[init_capacity_index];
    size = 0;
    table = new TreeMap[M]; //数组长度也是 M
    //数组的元素也要初始化
    for(int i = 0; i < M; i++) {
        table[i] = new TreeMap<>();
    }
}

//添加
public void add(K key, V value) {
    //先要看一下是否存在 (不存在才存储;否则是修改)
    TreeMap<K, V> map = table[hash(key)];
    map.put(key, value);
    if(!map.containsKey(key)) {
        //新添加
        size++;

        //添加完毕之后,要检查是否需要扩容
        if(size >= up_factor * M && init_capacity_index + 1 < capacity.length) {
            resize(capacity[++init_capacity_index]);
        }
    }
}

//删除
public V remove(K key) {
    TreeMap<K, V> map = table[hash(key)];

    V ret = null;
    //在相应的 map 中查找
    if(map.containsKey(key)) {
        ret = map.remove(key);
        //删除之后要维护 size
        size--;

        if(size < low_factor * M && init_capacity_index - 1 >=0 ) {
            init_capacity_index--;
            resize(capacity[init_capacity_index]);
        }
    }
    return ret;
}

均摊复杂度

把扩容和缩容均摊到其他的 add 和 remove 操作上。

从 N 个元素到 up_factor * M 个元素,扩容了一次,换句话说,每添加 (N-1)M 个元素才会加倍 1 次,此时相当于把 1 添加均摊到 (N-1)M 次操作上,故而可以忽略不计。所以平均而言,增加操作复杂度是 O(1)。

同理缩容也可以这样均摊,即删除操作涉及缩容时,均摊下来也是 O(1)。

不涉及扩容和缩容的 add, remove 呢?更是如此,O(1)。

所以,带有扩容机制的 Hash表,占用空间更大,但是时间效率却更高。

键的问题

因为内部查找表是采用的 TreeMap,它要求键是可比较的。(Hash结构则不要求)

可以这样改造:

AdvanceHashTable<K extends Comparable<K>, V>

但这样一来放入Hash表的键必须是可比较的,所谓鱼与熊掌,不可兼得。

相关练习

Leetcode 387

first unique char,找第一个不重复的字符。

first unique char

因为题目要求只在小写字母中寻找,所以完全可以用一个 26 个长度的数组来模拟hash表。

  • key 为字母相对于 ‘a’ 的偏移
  • value 为该字符在整个给定字符串中出现的频率

简单的两趟循环就解决了,出了循环还没有找到说明不存在:

class Solution {
    public int firstUniqChar(String s) {
        int[] freqs = new int[26];

        //统计 s 中各个字符的频率
        for(int i = 0; i < s.length(); i++) {
            freqs[s.charAt(i) - 'a']++;
        }

        //找到第一个不重复的字符
        for(int i = 0; i < s.length(); i++) {
            if(freqs[s.charAt(i) - 'a'] == 1) {
                return i;//返回查找到的索引
            }
        }
        return -1;        
    }
}

扩展

除了链地址法(后接查找表的方法)外,还有 开放地址法

开放地址法 是一个统称,即 每一个位置都对元素开放,符合占用规则,就能占用。具体实现也有很多种:

  • 线性探测法: 计算结果表明应该放在某个位置,但是那个位置被占用了,此时直接放在后面一个位置
    • 其改进,平方探测; (+1不行,+4, 再不行 +9,尽量分散存储)
  • 二次hash法: 多次哈希计算,每次hash函数不同 (多个哈希函数备选),即 hash1(key)冲突了,采用hash2(key)计算

开放地址没有查找表支持,都是直接在数组里面存储的,所以存在一个 负载率 的概念,选择得当,那么空间利用率就高。

  • 当然超过一定的负载,也要重新分配数组

(当然综合开放地址和封闭地址,也不是不可以; 总而言之,链地址法一般而言效率足够)

(除此之外,其实还有其他,但大都是理论研究,工程中用的其实比较少)


   转载规则


《纯数据结构Java实现(11/11)(散列)》 欧文 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录