散列表

Author Avatar
Brian Lee 9月 03, 2018
  • 在其它设备中阅读本文章

《Algorithm》(Sedgewick)笔记:散列表


原理

在记录的存储地址和它的关键字之间建立一个确定的对应关系;这样,理想状态下不经过比较,一次存取就能得到所查元素。

可以用算术操作将键转化为数组的索引来访问数组中的键值对。


步骤

第一步 :将被查找的键转化为数组的一个索引

第二步 :处理碰撞冲突(需要面对两个或多个键都会散列到相同的索引值的情况),两种方法:拉链法线性探测法


术语

散列表

又称哈希表,一个有限的连续的地址空间,用以容纳按哈希地址存储的记录。

散列函数

又称哈希函数,记录的存储位置与它的关键字之间存在的一种对应关系。

冲突

对于 $key_i\neq key_j$ ,$i\neq j$ ,出现 $H(key_i)=H(key_j)$ 的现象。


散列函数

正整数

最常用的方法是 除留余数法 ,选择大小为素数 $M$ 的数组,对于任意正整数 $k$ ,计算 $k$ 除以 $M$ 的余数。这种函数计算可以有效地将键散布在 $0$ 到 $M-1$ 的范围内。

$M$ 使用素数散列值的分布会更好。

浮点数

将键表示为二进制数然后再使用除留余数法。

字符串

int hash = 0;
for (int i = 0; i < s.length(); i++) {
      hash = (R * hash + s.charAt(i) % M);
}

$R$ 足够小,就可以将键散布在 $0$ 到 $M-1$ 的范围内。$R$ 一般取31。

组合键

以含有day、month、year的Date类为例,可以这样计算散列值:

int hash = (((day * R + month) % M) * R + year) % M

hashCode

Java中hashCode()方法实现了散列函数,但其返回的是对象的地址,即一个32位整数,所以可以将其和除留余数法结合起来产生一个 $0$ 到 $M -1$ 的整数,方法如下:

private int hash(Key x) {
  return (x.hashCode() & 0x7fffffff) % M;
}

这段代码将符号位屏蔽,然后用除留余数法计算散列值。


基于拉链法的散列表

原理

将大小为 $M$ 的数组中的每个元素指向一条链表,链表中的每个结点都存储了散列值为该元素的索引的键值对。

图示

拉链法

步骤

  1. 首先根据散列值找到对应的链表
  2. 沿着链表顺序查找相应的键

代码

public class SeperateChainingHashST<Key, Value> {
    private int N;  //键值对总数
    private int M;  //散列表大小(M条链表)
    private SequentialSearchST<Key, Value>[] st;    //存放链表对象的数组
    //构造函数,名创建M条链表
    public SeperateChainingHashST() {
        this(997);
    }
    public SeperateChainingHashST(int M) {
        this.M = M;
        st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
        for (int i = 0; i < M; i++)
            st[i] = new SequentialSearchST();
    }
    public int size() {
        return N;
    }
    public boolean isEmpty() {
        return size() == 0;
    }
    public boolean contains(Key key) {
        return get(key) != null;
    }
    //通过hashcode得到hash值
    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }
    public Value get(Key key) {
        return (Value) st[hash(key)].get(key);
    }
    public void put(Key key, Value val) {
        st[hash(key)].put(key, val);
    }
    public void delete(Key key) {
        int i = hash(key);
        if (st[i].contains(key))    N--;
        st[i].delete(key);
    }
    public Iterable<Key> keys() {
        Queue<Key> queue = new LinkedList<Key>();
        for (int i = 0; i < M; i++) {
            for (Key key : st[i].keys())
                queue.offer(key);
        }
        return queue;
    }
}

效率

查找与插入的时间复杂度为 $O(N/M)$

优缺点

优点
  • 实现简单
  • 在键的顺序不重要的应用中,它是最快的符号表实现
  • 冲突处理简单,无堆积现象,平均查找长度较短
  • 较适合于事先无法确定表长的情况
  • 删除结点的操作易于实现
缺点
  • 在键的顺序重要的应用中不适合(如快速找到最大最小键、查找某个范围的键等)

源代码

https://github.com/XutongLi/Algorithm-Learn/tree/master/src/S3_Searching/S3_4_Hash_Tables/S3_4_2_SeparateChainingHash


基于线性探测法的散列表

原理

采用大小为 $M$ 的数组保存 $N$ 个键值对,其中 $M>N$ 。需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为 开放地址散列表

开放地址散列表中最简单的方法叫做 线性探测法插入 时当碰撞发生时(当一个键的散列值已经被另一个不同的键占用),检查散列表中的下一个位置(索引增大,到达数组结尾时折回数组开头),直到遇到空位,将其插入到空位中。查找 时,若按照散列值找到的键不同,则继续查找下一位置,找到后返回对应键的值,若查找到空位,则返回空。

图示

线性探测法

代码

public class LinearProbingHashST<Key, Value> {
    private int N;  //符号表中键值对的总数
    private int M = 16; //线性探测表大小
    private Key[] keys; //键
    private Value[] vals;   //值
    public LinearProbingHashST() {
        this(16);
    }
    public LinearProbingHashST(int M) {
        this.M = M;
        keys = (Key[]) new Object[M];
        vals = (Value[]) new Object[M];
    }
    public int size() {
        return N;
    }
    public boolean isEmpty() {
        return N == 0;
    }
    public boolean contains(Key key) {
        return get(key) != null;
    }
    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }
    private void resize(int cap) {
        LinearProbingHashST<Key, Value> t;
        t = new LinearProbingHashST<>(cap);
        for (int i = 0; i < M; i++) {
            if (keys[i] != null)
                t.put(keys[i], vals[i]);
        }
        keys = t.keys;
        vals = t.vals;
        M = t.M;
    }
    public void put(Key key, Value val) {
        if (N >= M / 2) resize(2 * M);
        int i;
        for (i = hash(key); keys[i] != null; i = (i + 1) % M){
            if (keys[i].equals(key)) {
                vals[i] = val;
                return;
            }
        }
        keys[i] = key;
        vals[i] = val;
        N++;
    }
    public Value get(Key key) {
        for (int i = hash(key); keys[i] != null; i = (i + 1) % M)
            if (keys[i].equals(key))
                return vals[i];
        return null;
    }
    public void delete(Key key) {
        if (!contains(key)) return;
        int i = hash(key);
        while (!key.equals(keys[i]))
            i = (i + 1) % M;
        keys[i] = null;
        vals[i] = null;
        i = (i + 1) % M;
        while (keys[i] != null) {
            Key keyToRedo = keys[i];
            Value valToRedo = vals[i];
            keys[i] = null;
            vals[i] = null;
            N--;
            put(keyToRedo, valToRedo);
            i = (i + 1) % M;
        }
        N--;
        if (N > 0 && N <= M / 8)
            resize(M / 2);
    }
    public Iterable<Key> keys() {
        Queue<Key> queue = new LinkedList<>();
        for (int i = 0; i < M; i++)
            if (keys[i] != null)
                queue.offer(keys[i]);
        return queue;
    }
}

调整数组大小

研究表明,当散列表快满的时候查找所需的探测次数是巨大的($\alpha=N/M$ 越趋近于 $1$ ,探测的次数越大) ,但当使用率 $\alpha<1/2$ 时探测的预计次数只在 $1.5$ 到 $2.5$ 之间。

所以要动态调整数组大小,以保证 $\alpha$ 不大于 $1/2 $ 。

对于拉链法,如果可以准确地估计用例所需的散列表的大小 $N$ ,调整数组的工作不是必须的。

源代码

https://github.com/XutongLi/Algorithm-Learn/tree/master/src/S3_Searching/S3_4_Hash_Tables/S3_4_3_Linear_Probing_Hash


本博客采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!
本文链接:http://brianleelxt.top/2018/09/03/HashTable/