数据结构和算法分析ios

小白入门——哈希算法

2019-06-14  本文已影响11人  tomas家的小拨浪鼓

哈希

哈希（Hash）也称为散列，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，这个输出值就是散列值。

哈希表

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

散列表是算法在时间和空间上作出权衡的经典例子

如果没有内存限制，我们可以直接将键作为（可能是一个超大的）数组的索引，那么所有查找操作只需要访问内存一次即可完成。但这种理想情况不会经常出现，因为当键很多时需要的内存太大。另一方面，如果没有时间限制，我们可以使用无序数组并进行顺序查找，这样就只需要很少的内存。而散列表则使用了适度的空间和时间并在这两个极端之间找到了一种平衡。事实上，我们不必重写代码，只需要调整散列算法的参数就可以在空间和时间之间作出取舍。我们会使用概率论的经典结论来帮组我们选择适当的参数。

使用Hash的查询算法分为两步：

① 用Hash函数将被查找的键转化为数组的一个索引。
理想情况下，不同的键都能转化为不同的索引值。当然，这只是理想情况，所以我们需要面对两个或者多个键都会散列到相同的索引值的情况。
② 处理碰撞冲突的过程

Hash函数

一个好的Hash函数应满足下列两个要求：

几种常见的Hash算法：

① 除法哈希法

公式：hash(key) = key mod M

注意：M 通常为“素数”

② 乘法哈希法

公式：hash(key) = floor( M/W * ( a * key mod W) )
其中 floor 表示对表达式进行下取整

注意：

  1. 通常设置 M 为 2 的幂次方。
  2. W 为计算机字长大小（也为2的幂次方）。
  3. a 为一个非常接近于W的数。

其实，“乘法哈希”的思想就是：提取关键字 key 中间 k 位数字。

③ 斐波那契（Fibonacci）哈希法

也就是当 “乘法哈希法” 的 a ≈ W/φ，1/φ ≈ (√5-1)/2 = 0.618 033 988 时情况。而，1/φ ≈ (√5-1)/2 = 0.618 033 988，可称为黄金分割点。

Q：那，为什么“斐波那契（Fibonacci）哈希法”能够更好的将关键字 key 进行散列了?

A：Why is 'a ≈ W/φ' special? It has to do with what happens to consecutive keys when they are hashed using the multiplicative method. As shown in Figure ‘Fibonacci Hashing’ , consecutive keys are spread out quite nicely. In fact, when we use 'a ≈ W/φ' to hash consecutive keys, the hash value for each subsequent key falls in between the two widest spaced hash values already computed. Furthermore, it is a property of the golden ratio, φ , that each subsequent hash value divides the interval into which it falls according to the golden ratio!

常见的两种解决碰撞的方法

① 拉链法（separate chaining）
一个Hash函数能够将键转换为数组索引，Hash算法的第二部是碰撞处理，也就是处理两个或多个键的Hash值相同的情况。一种直接的办法是将大小为 M 的数组中的每个元素指向一条链表，链表中的每个结点都存储了Hash值为该元素的索引的键值对。这种方法被称为“拉链法”，因此发生冲突的元素都被存储在一个链表中。 
public class SeparateChainingHashST<Key, Value>
{
    private int N;                              // number of key-value pairs
    private int M;                              // hash table size
    private SequentialSearchST<Key, Value>[] st;    // array of ST objects
    public SeparateChainingHashST()
    {
        this(997);
    }
    public SeparateChainingHashST(int M)
    {
        // Create M linked lists.
        this.M = M;
        st = (SequentialSearchST<Key, Value>[])new SequentialSearchST[M];
        for (int i = 0; i < M; i++)
        {
            st[i] = new SequentialSearchST();
        }
    }
    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 Iterable<Key> keys()     // See Exercise 3.4.19
}

public class SequentialSearchST<Key, Value>
{
    private Node first;         // first node in the linked list
    private class Node
    {
        // linked-list node
        Key key;
        Value val;
        Node next;
        public Node(Key key, Value val, Node next)
        {
            this.key = key;
            this.val = val;
            this.next = next;
        }
    }
    public Value get(Key key)
    {
        // Search for key, return associated value.
        for (Node x = first; x != null; x = x.next)
        {
            if (key.equals(x.key))
            {
                return x.val;   // search hit
            }
        }
        return null;            // search miss
    }
    public void put(Key key, Value val)
    {
        // Search for key. Update value if found; grow table if new.
        for (Node x = first; x != null; x = x.next)
        {
            if (key.equals(x.key))
            {
                x.val = val;
                return;                     // Search hit : update val.
            }
        }
        first = new Node(key, val, first);  // Search miss: add new node.
    }
}
② 线性探测法（linear probing）
public class LinearProbingHashST<Key, Value>
{
    private int N;          // number of key-value pairs in the table
    private int M = 16;     // size of linear-probing table
    private Key[] keys;     // the keys
    private Value[] vals;   // the values
    public LinearProbingHashST()
    {
        keys = (Key[])new Object[M];
        vals = (Value[])new Object[M];
    }
    private int hash(Key key)
    {
        return (key.hashCode() & 0x7fffffff) % M;
    }
    private void resize()   // see page 474
    public void put(Key key, Value val)
    {
        if (N >= M/2)
        {
            resize(2*M);    // double M (see text)
        }
        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;
    }
}

要查找一个键，我们从它的Hash值开始顺序查找，如果找到则命中，如果遇到空元素则未命中。

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);
    }
}

假设J（均匀哈希假设）。我们使用的Hash函数能够均匀并独立地将所有的键散布于 0 到 M-1 之间。
讨论。我们在实现Hash函数时随意指定了很多参数，这显然无法实现一个能够在数学意义上均匀并独立地散布所有键的Hash函数。事实上，深入的理论研究报告告诉我们想要找到一个计算简单但又拥有一致性和均匀性的Hash函数是不太可能的。在实际应用中，和使用 Math.random() 生成随机数一样，大多数程序员都会满足于随机数生成器类的Hash函数。很少人会去检验独立性，而这个性质一般都不会满足。

命题 M ：在一张大小为 M 并含有 N = α * M 个键的基于线性探测的哈希表中，基于假设 J ，命中和未命中的查找所需的探测次数分别为：

特别是当 α 约为 1/2 时，查找命中所需要的探测次数约为 3/2，未命中所需要的约为 5/2。当 α 趋于 1 时，这些估计值的精确度会下降，但不需要担心这些情况，因为我们会保证哈希表的使用率小于 1/2。
当哈希表快满的时候查找所需的探测次数是巨大的（α 越趋近于1，由公式可知探测的次数也越来越大），但当使用率 α 小于 1/2 时探测的预计次数只在 1.5 到 2.5 之间。

参考：

Multiplication Method
Fibonacci Hashing
《算法 第4版》

上一篇下一篇

猜你喜欢

热点阅读