hashtable - ハッシュテーブルでは、キーは対応する値と共に格納されますか?

Question

例として、名前をキー、電話番号をデータとするハッシュテーブルを作成しています。名前と数字を組み合わせたテーブル (つまり、構造体のテーブル) にするか、数字だけのテーブルにするか? 誰かの電話番号を検索している場合、その名前は既にわかっているため、名前と番号を一緒に保存する意味がわかりません。

score 1 · Accepted Answer

直面しているいくつかの問題について、いくつかの一般的な提案があります。

辞書や電話帳など、何らかのキーに基づいてデータをすばやく検索したい場合は、 map を使用します。
値が一意で、演算子 < が定義されていて、迅速なルックアップが必要な場合は、セットを使用します。
繰り返し最大値が必要な場合は、priority_queue を使用します。
値をすばやく追加したいが、頻繁にアクセスする必要がない場合は、リストを使用します。
特定の位置の値にすばやくアクセスしたい場合は、ベクトルを使用します。

質問に戻りますが、HashTable は一定時間アクセスできるテーブルの実装です。マップと同様に、キーと値のペアの関連付けをハッシュテーブルに格納できます。ただし、ハッシュテーブルはデータを並べ替えた順序で格納しません。ハッシュテーブルは、最上位の配列で実装されます。各キーは、ハッシュ関数によって配列内のスロットにマップされます。しかし、各コンテナの最大の利点を得るために、コンテナを組み合わせると便利な場合があります。あなたの電話帳のように。

たとえば、複数のキータイプに基づいてレコードを検索するとします。

John-Romero 
5673-67854

Alice-Nice
3452-878

名前または電話番号を入力してレコードを検索できるようにしたいと考えています。したがって、各レコードに 2 つの検索キーが必要です。(すべてのキーが一意であると仮定します。) しかし、マップでは、レコードごとにキーを 1 つだけ持つことができます。1 つの解決策は、レコードのマスターリストを作成することです。キーの種類ごとに、電話帳のレコードを指す反復子を含むマップを作成します。

レコードの挿入を 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

hashtable - ハッシュテーブルでは、キーは対応する値と共に格納されますか?