hashtable - 在哈希表中，键是否与其对应的值一起存储？

Question

例如，我正在编写一个哈希表，其中名称作为键，电话号码作为数据。它应该是名称与数字组合的表（即结构表）还是仅包含数字的表？因为如果您正在查找某人的电话号码，您已经知道他们的姓名，所以我看不出将姓名与号码一起存储的意义。

score 1 · Accepted Answer

对于您面临的一些问题，有一些一般性建议：

如果您想根据某个键快速查找数据，例如在字典或 电话簿中，请使用 map。
如果值是唯一的，定义了运算符 <，并且您想要快速查找，请使用集合。
如果您反复想要最大值，请使用 priority_queue。
如果您想快速添加值但不需要经常访问它们，请使用列表。
如果要快速访问特定位置的值，请使用向量。

回到您的问题，HashTable 是具有恒定时间访问的表实现。像地图一样，您可以将键值对关联存储在哈希表中。但是，哈希表不按排序顺序存储数据。哈希表是用顶层的数组实现的。每个键通过哈希函数映射到数组中的一个槽。但有时将容器组合起来以获得每个容器的最佳优势很有用。就像你的电话簿一样。

例如，假设我们要查找基于多个键类型的记录。

John-Romero 
5673-67854

Alice-Nice
3452-878

我们希望能够通过输入他们的姓名或电话号码来查找记录。所以我们希望每条记录有 2 个搜索键。（我们假设所有键都是唯一的。）但是映射只允许我们每条记录只有一个键，一种解决方案是创建记录的主列表。对于每种键类型，创建一个映射，其中包含指向电话簿中记录的迭代器。

为了使记录插入 O(1)，列表对电话簿来说是很好的。

想象一个有 50,000 个姓名/号码配对的电话簿。每个数字都是一个 10 位数字。我们需要创建一个数据结构来查找与特定电话号码匹配的姓名。理想情况下，名称查找应该是 O(1) 的预期时间，并且呼叫者 ID 系统应该使用 O(n) 内存（n = 50,000）。

list<Record> phone_book;

为了进行 O(1) 的查找，映射最适合键。

map<string, list<Record>::iterator> names;
map<int, list<Record>::iterator> phones;

我们可以通过取消引用迭代器来打印记录：

cout << *names["John-Romero"];

这是一个带有单个键的 Java 示例程序

import java.util.*;
public class PhoneBook {

    /**
     * @param args the command line arguments.
     */
    public static void main(String[] args) {
        /* instantiate a Hashtable Object*/
        Hashtable dict = new Hashtable();
        /* it is just an iterator */
        Enumeration iterator;
        /* the temporary key value*/
        String tempKey;
        /* here we put some key and value */
        dict.put("Zahurul Islam",new Long(898989));
        dict.put("Naushad Uzzaman", new Long(676767));
        dict.put("Asif Iqbal", new Long(565656));
        dict.put("Mr.Pavel", new Long(232323));
        dict.put("Marzy Rahman",new Long(343434));
        dict.put("Mehedi Al mamun",new Long(234324));

        /* here we traverse the dict */
        iterator = dict.keys();
        while (iterator.hasMoreElements()) {
            Object key = iterator.nextElement();
            System.out.println("Name: "+ key +" Phone Number: "+ dict.get(key));
        }

        /* this is temporay key, if this is exist we just change the value
         * other wise we put the pair(key,value)  */
        tempKey = "Zahurul Islam";
        if(!dict.containsKey(tempKey)) {
            System.out.println("No such Name in this phone Book");
        } else {
            Long phoneNumber = (Long) dict.get(tempKey);
            long phNum = phoneNumber.longValue();
            System.out.println(phNum+ " This Phone Number of "+ tempKey + " is changed ");
            dict.put(tempKey, new Long(121212));
        }

        System.out.println("\nUpdated Phone book\n");
        iterator = dict.keys();
        while (iterator.hasMoreElements()) {
            Object key = iterator.nextElement();
            System.out.println("Name: "+ key +" Phone Number: "+ dict.get(key));
        }



    }

}

这是其他带有 2 键的

import java.io.*;
import java.lang.reflect.Array;
import static java.lang.System.out;
import java.util.*;

/************************************************************************************
 * This class provides hash maps that use the hashing with separate chaining algorithm.
 * A hash table is created that is an array of buckets.  It restricts the number of
 * slots per bucket to one (just one key-value pair), but could easily be extended
 * to support multiple key-value pairs per bucket.
 */
public class HashSC <K, V>
       extends AbstractMap <K, V>
       implements Serializable, Cloneable, Map <K, V>
{
    /********************************************************************************
     * This inner class defines buckets that are stored in the hash table.
     */
    private class Bucket
    {
        K      key;       // alt. use K [] instead of K
        V      value;     // alt. use V [] instead of V
        Bucket next;
        Bucket (K k, V v, Bucket n) { key = k; value = v; next = n; }
    } // Bucket inner class

    /** The array of buckets making up the hash table.
     */
    private final Bucket [] hTable;

    /** The size of the hash table (number of home buckets)
     */
    private final int size;

    /** Counter for the number buckets accessed (for performance testing)
     */
    private int count = 0;

    /********************************************************************************
     * Construct a hash table that uses separate chaining.
     * @param cap  the capacity of the hash table
     */
    @SuppressWarnings("unchecked")
    public HashSC (int cap)
    {
        hTable = (Bucket []) Array.newInstance (Bucket.class, size = cap);
    } // HashSC

    /********************************************************************************
     * Return a set view of map containing all the entries as pairs of keys and values.
     * @return  the set view of the map
     */
    public Set <Map.Entry <K, V>> entrySet ()
    {
        Set <Map.Entry <K, V>> enSet = new HashSet <> ();
        for (int i = 0; i < size; i++) {
            for (Bucket b = hTable [i]; b != null; b = b.next) {
                enSet.add (new AbstractMap.SimpleEntry <K, V> (b.key, b.value));
            } // for
        } // for

        return enSet;
    } // entrySet

    /********************************************************************************
     * Given the key, look up the value in the hash table.
     * @param key  the key used for look up
     * @return  the value associated with the key
     */
    public V get (Object key)
    {
        int i = h (key);
        for (Bucket b = hTable [i]; b != null; b = b.next) {
            count++;
            if (b.key.equals (key)) return b.value;
        } // for
        return null;
    } // get

    /********************************************************************************
     * Put the key-value pair in the hash table.
     * @param key    the key to insert
     * @param value  the value to insert
     * @return  null (not the previous value)
     */
    public V put (K key, V value)
    {
        int i = h (key);
        hTable [i] = new Bucket (key, value, hTable [i]);
        return null;
    } // put

    /********************************************************************************
     * Return the size (number of home buckets) in the hash table. 
     * @return  the size of the hash table
     */
    public int size ()
    {
        return size;
    } // size

    /********************************************************************************
     * Print the hash table.
     */
    private void print ()
    {
        out.println ("Hash Table (hashing with separate chaining)");
        out.println ("-------------------------------------------");
        for (int i = 0; i < size; i++) {
            out.print (i + ":\t");
            boolean notFirst = false;
            for (Bucket b = hTable [i]; b != null; b = b.next) {
                if (notFirst) out.print ("--> ");
                out.print ("[ " + b.key + " ]\t");
                notFirst = true;
            } // for
            out.println ();
        } // for
        out.println ("-------------------------------------------");
    } // print

    /********************************************************************************
     * Hash the key using the hash function.
     * @param key  the key to hash
     * @return  the location of the bucket chain containing the key-value pair
     */
    private int h (Object key)
    {
        return key.hashCode () % size;
    } // h

    /********************************************************************************
     * The main method used for testing.
     * @param  the command-line arguments (args [0] gives number of keys to insert)
     */
    public static void main (String [] args)
    {
        HashSC <Integer, Integer> ht_i = new HashSC <> (11);
        HashSC <String, Integer>  ht_s = new HashSC <> (11);
        int nKeys = 30;
        if (args.length == 1) nKeys = Integer.valueOf (args [0]);
        for (int i = 1; i < nKeys; i += 2) {
            ht_i.put (i, i * i);
            ht_s.put ("s" + i, i * i);
        } // for
        ht_i.print ();
        ht_s.print ();
        for (int i = 0; i < nKeys; i++) {
            out.println ("key = " + i + "  value = " + ht_i.get (i));
            out.println ("key = s" + i + " value = " + ht_s.get ("s" + i));
        } // for
        out.println ("-------------------------------------------");
        out.println ("Average number of buckets accessed = " + ht_i.count / (double) nKeys);
        out.println ("Average number of buckets accessed = " + ht_s.count / (double) nKeys);
    } // main

} // HashSC class

我认为您可以比较两种解决方案的效率（最后一个代码需要修改为电话簿），以便您决定哪个更适合您的需求。

hashtable - 在哈希表中，键是否与其对应的值一起存储？

1 回答 1

Related

Reference