`
sunwinner
  • 浏览: 202199 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

基础数据结构和算法十二:Hash table

阅读更多

 

Search algorithms that use hashing consist of two separate parts. The first part is to compute a hash function that transforms the search key into an array index. Ideally, different keys would map to different indices. This ideal is generally beyond our reach, so we have to face the possibility that two or more different keys may hash to the same array index. Thus, the second part of a hashing search is a collision-resolution process that deals with this situation. After describing ways to compute hash functions, we shall consider two different approaches to collision resolution: separate chaining and linear probing.

 

Hash functions The first problem that we face is the computation of the hash function, which transforms keys into array indices. If we have an array that can hold M key-value pairs, then we need a hash function that can transform any given key into an index into that array: an integer in the range [0, M–1]. We seek a hash function that both is easy to compute and uniformly distributes the keys: for each key, every integer between 0 and M – 1 should be equally likely (independently for every key). This ideal is somewhat mysterious; to understand hashing, it is worthwhile to begin by thinking carefully about how to implement such a function.

 

 

The hash function depends on the key type. Strictly speaking, we need a different hash function for each key type that we use. If the key involves a number, such as a social security number, we could start with that number; if the key involves a string, such as a person’s name, we need to convert the string into a number; and if the key has multiple parts, such as a mailing address, we need to combine the parts somehow. For many common types of keys, we can make use of default implementations provided by Java.

 

we have three primary requirements in implementing a good hash function for a given data type:

It should be consistent—equal keys must produce the same hash value.

It should be efficient to compute.

It should uniformly distribute the keys.

 

Satisfying these requirements simultaneously is a job for experts. As with many built-in capabilities, Java programmers who use hashing assume that hashCode() does the job, absent any evidence to the contrary.

 

 

Hashing with separate chaining A hash function converts keys into array indices. The second component of a hashing algorithm is collision resolution: a strategy for handling the case when two or more keys to be inserted hash to the same index. A straightforward and general approach to collision resolution is to build, for each of the M array indices, a linked list of the key-value pairs whose keys hash to that index. This method is known as separate chaining because items that collide are chained together in separate linked lists. The basic idea is to choose M to be sufficiently large that the lists are sufficiently short to enable efficient search through a two-step process: hash to find the list that could contain the key, then sequentially search through that list for the key.

public class SeparateChainingHashST<Key, Value> {
    private static final int INIT_CAPACITY = 4;

    // largest prime <= 2^i for i = 3 to 31
    // not currently used for doubling and shrinking
    // private static final int[] PRIMES = {
    //    7, 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381,
    //    32749, 65521, 131071, 262139, 524287, 1048573, 2097143, 4194301,
    //    8388593, 16777213, 33554393, 67108859, 134217689, 268435399,
    //    536870909, 1073741789, 2147483647
    // };

    private int N;                                // number of key-value pairs
    private int M;                                // hash table size
    private SequentialSearchST<Key, Value>[] st;  // array of linked-list symbol tables


    // create separate chaining hash table
    public SeparateChainingHashST() {
        this(INIT_CAPACITY);
    }

    // create separate chaining hash table with M lists
    public SeparateChainingHashST(int M) {
        this.M = M;
        st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
        for (int i = 0; i < M; i++)
            st[i] = new SequentialSearchST<Key, Value>();
    }

    // resize the hash table to have the given number of chains b rehashing all of the keys
    private void resize(int chains) {
        SeparateChainingHashST<Key, Value> temp = new SeparateChainingHashST<Key, Value>(chains);
        for (int i = 0; i < M; i++) {
            for (Key key : st[i].keys()) {
                temp.put(key, st[i].get(key));
            }
        }
        this.M = temp.M;
        this.N = temp.N;
        this.st = temp.st;
    }

    // hash value between 0 and M-1
    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    // return number of key-value pairs in symbol table
    public int size() {
        return N;
    }

    // is the symbol table empty?
    public boolean isEmpty() {
        return size() == 0;
    }

    // is the key in the symbol table?
    public boolean contains(Key key) {
        return get(key) != null;
    }

    // return value associated with key, null if no such key
    public Value get(Key key) {
        int i = hash(key);
        return st[i].get(key);
    }

    // insert key-value pair into the table
    public void put(Key key, Value val) {
        if (val == null) {
            delete(key);
            return;
        }

        // double table size if average length of list >= 10
        if (N >= 10 * M) resize(2 * M);

        int i = hash(key);
        if (!st[i].contains(key)) N++;
        st[i].put(key, val);
    }

    // delete key (and associated value) if key is in the table
    public void delete(Key key) {
        int i = hash(key);
        if (st[i].contains(key)) N--;
        st[i].delete(key);

        // halve table size if average length of list <= 1
        if (M > INIT_CAPACITY && N <= 2 * M) resize(M / 2);
    }

    // return keys in symbol table as an Iterable
    public Iterable<Key> keys() {
        Queue<Key> queue = new Queue<Key>();
        for (int i = 0; i < M; i++) {
            for (Key key : st[i].keys())
                queue.enqueue(key);
        }
        return queue;
    }
}
public class SequentialSearchST<Key, Value> {
    private int N;           // number of key-value pairs
    private Node first;      // the linked list of key-value pairs

    // a helper linked list data type
    private class Node {
        private Key key;
        private Value val;
        private Node next;

        public Node(Key key, Value val, Node next) {
            this.key = key;
            this.val = val;
            this.next = next;
        }
    }

    // return number of key-value pairs
    public int size() {
        return N;
    }

    // is the symbol table empty?
    public boolean isEmpty() {
        return size() == 0;
    }

    // does this symbol table contain the given key?
    public boolean contains(Key key) {
        return get(key) != null;
    }

    // return the value associated with the key, or null if the key is not present
    public Value get(Key key) {
        for (Node x = first; x != null; x = x.next) {
            if (key.equals(x.key)) return x.val;
        }
        return null;
    }

    // add a key-value pair, replacing old key-value pair if key is already present
    public void put(Key key, Value val) {
        if (val == null) {
            delete(key);
            return;
        }
        for (Node x = first; x != null; x = x.next)
            if (key.equals(x.key)) {
                x.val = val;
                return;
            }
        first = new Node(key, val, first);
        N++;
    }

    // remove key-value pair with given key (if it's in the table)
    public void delete(Key key) {
        first = delete(first, key);
    }

    // delete key in linked list beginning at Node x
    // warning: function call stack too large if table is large
    private Node delete(Node x, Key key) {
        if (x == null) return null;
        if (key.equals(x.key)) {
            N--;
            return x.next;
        }
        x.next = delete(x.next, key);
        return x;
    }


    // return all keys as an Iterable
    public Iterable<Key> keys() {
        Queue<Key> queue = new Queue<Key>();
        for (Node x = first; x != null; x = x.next)
            queue.enqueue(x.key);
        return queue;
    }
}

In a separate-chaining hash table with M lists and N keys,the probability that the number of keys in a list is within a small constant factor of N/M is extremely close to 1, the number of compares (equality tests) for search miss and insert is ~N/M.

 

 

Hashing with linear probing Another approach to implementing hashing is to store N key-value pairs in a hash table of size M > N, relying on empty entries in the table to help with collision resolution. Such methods are called open-addressing hashing methods.

The simplest open-addressing method is called linear probing: when there is a collision (when we hash to a table index that is already occupied with a key different from the search key), then we just check the next entry in the table (by incrementing the index). Linear probing is characterized by identifying three possible outcomes:

Key equal to search key: search hit

Empty position (null key at indexed position): search miss

Key not equal to search key: try next entry

We hash the key to a table index, check whether the search key matches the key there, and continue (incrementing the index, wrapping back to the beginning of the table if we reach the end) until finding either the search key or an empty table entry. It is customary to refer to the operation of determining whether or not a given table entry holds an item whose key is equal to the search key as a probe. We use the term interchangeably with the term compare that we have been using, even though some probes are tests for null.

The essential idea behind hashing with open addressing is this: rather than using memory space for references in linked lists, we use it for the empty entries in the hash table, which mark the ends of probe sequences. 

 

Deletion. How do we delete a key-value pair from a linear-probing table? If you think about the situation for a moment, you will see that setting the key’s table position to null will not work, because that might prematurely terminate the search for a key that was inserted into the table later. As an example, suppose that we try to delete C in this way in our trace example, then search for H. The

 

hash value for H is 4, but it sits at the end of the cluster, in position 7. If we set position 5 to null, then get() will not find H. As a consequence, we need to reinsert into the table all of the keys in the cluster to the right of the deleted key, this process is trickier than it might seem.

public class LinearProbingHashST<Key, Value> {
    private static final int INIT_CAPACITY = 4;

    private int N;           // number of key-value pairs in the symbol table
    private int M;           // size of linear probing table
    private Key[] keys;      // the keys
    private Value[] vals;    // the values


    // create an empty hash table - use 16 as default size
    public LinearProbingHashST() {
        this(INIT_CAPACITY);
    }

    // create linear proving hash table of given capacity
    public LinearProbingHashST(int capacity) {
        M = capacity;
        keys = (Key[]) new Object[M];
        vals = (Value[]) new Object[M];
    }

    // return the number of key-value pairs in the symbol table
    public int size() {
        return N;
    }

    // is the symbol table empty?
    public boolean isEmpty() {
        return size() == 0;
    }

    // does a key-value pair with the given key exist in the symbol table?
    public boolean contains(Key key) {
        return get(key) != null;
    }

    // hash function for keys - returns value between 0 and M-1
    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    // resize the hash table to the given capacity by re-hashing all of the keys
    private void resize(int capacity) {
        LinearProbingHashST<Key, Value> temp = new LinearProbingHashST<Key, Value>(capacity);
        for (int i = 0; i < M; i++) {
            if (keys[i] != null) {
                temp.put(keys[i], vals[i]);
            }
        }
        keys = temp.keys;
        vals = temp.vals;
        M = temp.M;
    }

    // insert the key-value pair into the symbol table
    public void put(Key key, Value val) {
        if (val == null) delete(key);

        // double table size if 50% full
        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++;
    }

    // return the value associated with the given key, null if no such value
    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;
    }

    // delete the key (and associated value) from the symbol table
    public void delete(Key key) {
        if (!contains(key)) return;

        // find position i of key
        int i = hash(key);
        while (!key.equals(keys[i])) {
            i = (i + 1) % M;
        }

        // delete key and associated value
        keys[i] = null;
        vals[i] = null;

        // rehash all keys in same cluster
        i = (i + 1) % M;
        while (keys[i] != null) {
            // delete keys[i] an vals[i] and reinsert
            Key keyToRehash = keys[i];
            Value valToRehash = vals[i];
            keys[i] = null;
            vals[i] = null;
            N--;
            put(keyToRehash, valToRehash);
            i = (i + 1) % M;
        }

        N--;

        // halves size of array if it's 12.5% full or less
        if (N > 0 && N <= M / 8) resize(M / 2);

        assert check();
    }

    // return all of the keys as in Iterable
    public Iterable<Key> keys() {
        Queue<Key> queue = new Queue<Key>();
        for (int i = 0; i < M; i++)
            if (keys[i] != null) queue.enqueue(keys[i]);
        return queue;
    }

    // integrity check - don't check after each put() because
    // integrity not maintained during a delete()
    private boolean check() {

        // check that hash table is at most 50% full
        if (M < 2 * N) {
            System.err.println("Hash table size M = " + M + "; array size N = " + N);
            return false;
        }

        // check that each key in table can be found by get()
        for (int i = 0; i < M; i++) {
            if (keys[i] == null) continue;
            else if (get(keys[i]) != vals[i]) {
                System.err.println("get[" + keys[i] + "] = " + get(keys[i]) + "; vals[i] = " + vals[i]);
                return false;
            }
        }
        return true;
    }
}

 

 

分享到:
评论

相关推荐

    数据结构和算法分析的PHP描述

    理解和掌握好数据结构与算法对于提高软件开发效率、优化代码性能至关重要。 #### 线性结构 线性结构是最基本的数据结构之一,包括数组、链表、栈、队列等。 ##### 数组(Array) **概述** 数组是一种简单的线性数据...

    Java数据结构和算法中文第二版

    根据提供的信息,“Java数据结构和算法中文第二版”这本书主要关注的是数据结构与算法的相关内容。下面将基于这些信息,详细介绍数据结构与算法的核心概念、重要性和应用领域,以及在Java编程环境中如何实现这些概念...

    数据结构与算法分析:php语言描述

    本篇文章将深入探讨在PHP中如何理解和实现各种重要的数据结构与算法。我们将会从数组、链表到更复杂的树形结构以及堆和散列表等进行逐一解析,并通过实际代码示例来帮助读者更好地掌握这些核心概念。 #### 数组...

    数据结构与算法教程(C++版)实验和课程设计

    - **哈希表(Hash Table)**:哈希表是一种使用哈希函数将键映射到值的数据结构,可以实现高效的查找、插入和删除操作。 #### 3. 算法基础 - **排序算法(Sorting Algorithms)**: - **冒泡排序(Bubble Sort)**:...

    java数据结构和算法学习笔记

    通过以上内容的总结,我们可以看出Java数据结构与算法的学习涵盖了从基础知识到具体应用的各个方面,对于软件开发人员来说非常重要。掌握这些知识不仅可以提高代码质量和效率,还能更好地理解和解决实际问题。

    前端大厂最新面试题-hash-table.docx

    * Hash Table 是一种数据结构,通过哈希函数将关键字映射到索引,以便快速访问和查找元素。 * Hash Table 由数组和哈希函数组成,哈希函数将关键字转换为数组的索引。 二、哈希函数 * 哈希函数是将关键字转换为...

    数据结构与算法分析 java语言描述第三版 源代码

    数据结构与算法分析是计算机科学中的核心...以上这些文件涵盖了数据结构和算法分析中的重要概念,包括排序、查找、树结构和哈希表,这些都是计算机科学和软件开发的基础。掌握这些知识对于理解和编写高效代码至关重要。

    《数据结构与算法:javaScript 描述》 代码合集.zip

    《数据结构与算法:JavaScript 描述》代码合集.zip是一个包含与数据结构和算法相关的JavaScript源码实践项目,主要关注数据采集、处理和展示。这个压缩包中的数据-practice-master目录下,很可能是包含了多个练习...

    Java数据结构与算法书中源码

    在IT领域,尤其是在软件开发中,理解和掌握数据结构与算法是至关重要的。这些技术构成了程序设计的基础,影响着代码的效率、可维护性和性能。针对提供的文件列表,我们可以深入探讨以下几个Java数据结构与算法的知识...

    数据结构与算法-JavaScript描述

    数据结构与算法是计算机科学的基础,对于任何编程语言来说,理解和掌握它们都是至关重要的,JavaScript也不例外。本资源“数据结构与算法-JavaScript描述”显然是一本专注于将这些概念应用于JavaScript编程的电子书...

    漫画算法之基础数据结构总结

    散列表(Hash Table)是实现散列的一种常见数据结构,它提供常数时间的查找、插入和删除操作。然而,实际应用中总会遇到冲突,常见的解决策略有开放寻址法和链地址法。 数组和链表是两种基本的线性数据结构。数组是...

    数据结构和算法分析.zip

    数据结构和算法分析是计算机科学中的核心领域,它关乎如何高效地存储、组织和操作数据。数据结构可以被看作是特定方式下数据的组织形式,而算法则是解决特定问题的步骤或指令集。理解并掌握这两者对于任何IT专业人员...

    算法程序实例(数据结构与算法-程序、素材)

    数据结构与算法是计算机科学的基础,它们构成了编程和软件开发的核心。这个压缩包"算法程序实例(数据结构与算法-程序、素材)"很显然是为了帮助学习者深入理解这些概念而提供的实践材料。以下是对其中可能包含的内容...

Global site tag (gtag.js) - Google Analytics