34

この質問のポイントは、さまざまな言語で配列を使用したハッシュテーブルの実装例のリストを収集することです。また、誰かがそれらがどのように機能するか、および各例で何が起こっているかについて、かなり詳細な概要を説明してくれるとよいでしょう。

編集：

特定の言語で組み込みのハッシュ関数を使用しないのはなぜですか?

ハッシュテーブルがどのように機能するかを理解し、それらを実装できる必要があるためです。これはそれほど重要なトピックではないように思えるかもしれませんが、最もよく使用されるデータ構造の 1 つがどのように機能するかを知ることは、私にとって非常に重要なことのように思えます。これがプログラミングのウィキペディアになる場合、これらは私がここに来るいくつかのタイプの質問です. 私は、ここで書かれる CS の本を探しているわけではありません。Intro to Algorithms を棚から取り出して、ハッシュ テーブルに関する章を読み、そのタイプの情報を取得することができました。より具体的には、コード例を探しています。特に私だけでなく、いつか同様の情報を検索してこのページに出くわす可能性のある他の人にとっても.

より具体的に言えば、それらを実装する必要があり、組み込み関数を使用できない場合、どのようにしますか?

ここにコードを入れる必要はありません。ペーストビンに入れてリンクするだけです。

4

9 に答える 9

20

ハッシュ テーブルは、一定時間内にアイテムを検索できるデータ構造です。値をハッシュし、その値を配列内のオフセットに変換することで機能します。ハッシュ テーブルの概念は非常に理解しやすいですが、実装は明らかに困難です。ここにハッシュ テーブル全体を貼り付けるわけではありませんが、数週間前に C で作成したハッシュ テーブルの一部を以下に示します...

ハッシュ テーブルを作成するための基本の 1 つは、優れたハッシュ関数を使用することです。ハッシュ テーブルで djb2 ハッシュ関数を使用しました。

int ComputeHash(char* key)
{
    int hash = 5381;
    while (*key)
    hash = ((hash << 5) + hash) + *(key++);
    return hash % hashTable.totalBuckets;
}

次に、テーブル内のバケットを作成および管理するための実際のコード自体が続きます

typedef struct HashTable{
    HashTable* nextEntry;
    char*      key;
    char*      value;
}HashBucket;

typedef struct HashTableEntry{
    int totalBuckets;       // Total number of buckets allocated for the hash table
    HashTable** hashBucketArray; // Pointer to array of buckets
}HashTableEntry;
HashTableEntry hashTable;

bool InitHashTable(int totalBuckets)
{
    if(totalBuckets > 0)
    {
        hashTable.totalBuckets = totalBuckets;
        hashTable.hashBucketArray = (HashTable**)malloc(totalBuckets * sizeof(HashTable));
        if(hashTable.hashBucketArray != NULL)
        {
            memset(hashTable.hashBucketArray, 0, sizeof(HashTable) * totalBuckets);
            return true;
        }
    }
    return false;
}

bool AddNode(char* key, char* value)
{
    int offset = ComputeHash(key);
    if(hashTable.hashBucketArray[offset] == NULL)
    {
        hashTable.hashBucketArray[offset] = NewNode(key, value);
        if(hashTable.hashBucketArray[offset] != NULL)
            return true;
    }

    else
    {
        if(AppendLinkedNode(hashTable.hashBucketArray[offset], key, value) != NULL)
            return true;
    }
    return false;
}

HashTable* NewNode(char* key, char* value)
{
    HashTable* tmpNode = (HashTable*)malloc(sizeof(HashTable));
    if(tmpNode != NULL)
    {
        tmpNode->nextEntry = NULL;
        tmpNode->key   = (char*)malloc(strlen(key));
        tmpNode->value = (char*)malloc(strlen(value));

        strcpy(tmpNode->key, key);
        strcpy(tmpNode->value, value);
    }
    return tmpNode;
}

AppendLinkedNode は、リンクされたリストの最後のノードを見つけて、それに新しいノードを追加します。

コードは次のように使用されます。

if(InitHashTable(100) == false) return -1;
AddNode("10", "TEN");

ノードの検索は次のように簡単です。

HashTable* FindNode(char* key)
{
    int offset = ComputeHash(key);
    HashTable* tmpNode = hashTable.hashBucketArray[offset];
    while(tmpNode != NULL)
    {
        if(strcmp(tmpNode->key, key) == 0)
            return tmpNode;
        tmpNode = tmpNode->nextEntry;
    }
    return NULL;
}

そして、次のように使用されます。

char* value = FindNode("10");
于 2008-08-24T21:40:55.187 に答える
8

< 60 LoC での Java 実装

import java.util.ArrayList;
import java.util.List;
import java.util.Random;


public class HashTable {

    class KeyValuePair {

        Object key;

        Object value;

        public KeyValuePair(Object key, Object value) {
            this.key = key;
            this.value = value;
        }
    }

    private Object[] values;

    private int capacity;

    public HashTable(int capacity) {
        values = new Object[capacity];
        this.capacity = capacity;
    }

    private int hash(Object key) {
        return Math.abs(key.hashCode()) % capacity;
    }

    public void add(Object key, Object value) throws IllegalArgumentException {

        if (key == null || value == null)
            throw new IllegalArgumentException("key or value is null");

        int index = hash(key);

        List<KeyValuePair> list;
        if (values[index] == null) {
            list = new ArrayList<KeyValuePair>();
            values[index] = list;

        } else {
            // collision
            list = (List<KeyValuePair>) values[index];
        }

        list.add(new KeyValuePair(key, value));
    }

    public Object get(Object key) {
        List<KeyValuePair> list = (List<KeyValuePair>) values[hash(key)];
        if (list == null) {
            return null;
        }
        for (KeyValuePair kvp : list) {
            if (kvp.key.equals(key)) {
                return kvp.value;
            }
        }
        return null;
    }

    /**
     * Test
     */
    public static void main(String[] args) {

        HashTable ht = new HashTable(100);

        for (int i = 1; i <= 1000; i++) {
            ht.add("key" + i, "value" + i);
        }

        Random random = new Random();
        for (int i = 1; i <= 10; i++) {
            String key = "key" + random.nextInt(1000);
            System.out.println("ht.get(\"" + key + "\") = " + ht.get(key));
        }   
    }
}
于 2012-06-17T01:53:23.667 に答える
7

HashTable は非常に単純な概念です。これは、キーと値のペアが (連想配列のように) 次のスキームによって配置される配列です。

ハッシュ関数は、(できれば) 未使用のインデックスへのキーを配列にハッシュします。値は、その特定のインデックスで配列に配置されます。

配列へのインデックスはハッシュ関数を介して計算できるため、データの取得は簡単です。したがって、ルックアップは ~ O(1) です。

ハッシュ関数が 2 つの異なるキーを同じインデックスにマップすると問題が発生します...これを処理するには多くの方法がありますが、ここでは詳しく説明しません...

ハッシュ テーブルは、データをすばやく格納および取得するための基本的な方法であり、ほぼすべてのプログラミング言語ライブラリに "組み込まれています"。

于 2008-08-24T21:09:30.037 に答える
1

これは、Java で実装されたハッシュ テーブルのコードです。軽微な問題があります - キー フィールドと値フィールドが同じではありません。今後編集するかもしれません。

public class HashTable
{
    private LinkedList[] hashArr=new LinkedList[128];
    public static int HFunc(int key)
    {
        return key%128;
    }


    public boolean Put(Val V)
    {

        int hashval = HFunc(V.getKey());
        LinkedNode ln = new LinkedNode(V,null);
        hashArr[hashval].Insert(ln);
        System.out.println("Inserted!");
        return true;            
    }

    public boolean Find(Val V)
    {
        int hashval = HFunc(V.getKey());
        if (hashArr[hashval].getInitial()!=null && hashArr[hashval].search(V)==true)
        {
            System.out.println("Found!!");
            return true;
        }
        else
        {
            System.out.println("Not Found!!");
            return false;
        }

    }
    public boolean delete(Val v)
    {
        int hashval = HFunc(v.getKey());
        if (hashArr[hashval].getInitial()!=null && hashArr[hashval].delete(v)==true)
        {
            System.out.println("Deleted!!");
            return true;
        }
        else 
        {
            System.out.println("Could not be found. How can it be deleted?");
            return false;
        }
    }

    public HashTable()
    {
        for(int i=0; i<hashArr.length;i++)
            hashArr[i]=new LinkedList();
    }

}

class Val
{
    private int key;
    private int val;
    public int getKey()
    {
        return key;
    }
    public void setKey(int k)
    {
        this.key=k;
    }
    public int getVal()
    {
        return val;
    }
    public void setVal(int v)
    {
        this.val=v;
    }
    public Val(int key,int value)
    {
        this.key=key;
        this.val=value;
    }
    public boolean equals(Val v1)
    {
        if (v1.getVal()==this.val)
        {
            //System.out.println("hello im here");
            return true;
        }
        else 
            return false;
    }
}

class LinkedNode
{
    private LinkedNode next;
    private Val obj;
    public LinkedNode(Val v,LinkedNode next)
    {
        this.obj=v;
        this.next=next;
    }
    public LinkedNode()
    {
        this.obj=null;
        this.next=null;
    }
    public Val getObj()
    {
        return this.obj;    
    }
    public void setNext(LinkedNode ln)
    {
        this.next = ln;
    }

    public LinkedNode getNext()
    {
        return this.next;
    }
    public boolean equals(LinkedNode ln1, LinkedNode ln2)
    {
        if (ln1.getObj().equals(ln2.getObj()))
        {
            return true;
        }
        else 
            return false;

    }

}

class LinkedList
{
    private LinkedNode initial;
    public LinkedList()
    {
        this.initial=null;
    }
    public LinkedList(LinkedNode initial)
    {
        this.initial = initial;
    }
    public LinkedNode getInitial()
    {
        return this.initial;
    }
    public void Insert(LinkedNode ln)
    {
        LinkedNode temp = this.initial;
        this.initial = ln;
        ln.setNext(temp);
    }
    public boolean search(Val v)
    {
        if (this.initial==null)
            return false;
        else 
        {
            LinkedNode temp = this.initial;
            while (temp!=null)
            {
                //System.out.println("encountered one!");
                if (temp.getObj().equals(v))
                    return true;
                else 
                    temp=temp.getNext();
            }
            return false;
        }

    }
    public boolean delete(Val v)
    {
        if (this.initial==null)
            return false;
        else 
        {
            LinkedNode prev = this.initial;
            if (prev.getObj().equals(v))
            {
                this.initial = null;
                return true;
            }
            else
            {
                LinkedNode temp = this.initial.getNext();
            while (temp!=null)
            {
                if (temp.getObj().equals(v))
                {
                    prev.setNext(temp.getNext());
                    return true;
                }
                else
                {
                    prev=temp;
                    temp=temp.getNext();
                }
            }
            return false;
            }
        }
    }
}
于 2009-07-18T20:44:34.940 に答える
0

もう少し具体的にする必要があると思います。次のオプションに関して、ハッシュテーブルにはいくつかのバリエーションがあります

  • ハッシュテーブルは固定サイズですか、それとも動的ですか?
  • どのタイプのハッシュ関数が使用されていますか?
  • ハッシュテーブルのサイズが変更された場合、パフォーマンス上の制約はありますか?

リストは延々と続く可能性があります。これらの各制約により、任意の言語で複数の実装が発生する可能性があります。

個人的には、選択した言語で利用できる組み込みのハッシュテーブルを使用するだけです。独自の実装を検討する唯一の理由は、パフォーマンスの問題によるものであり、それでも既存の実装のほとんどを打ち負かすことは困難です。

于 2008-08-24T19:37:37.060 に答える
0

指定された一連のキーと値のペアからハッシュ テーブルを構築し、指定されたキーに関連付けられた値のハッシュ テーブルを検索する関数を返す関数としての F# での最小限の実装:

> let hashtbl xs =
    let spine = [|for _ in xs -> ResizeArray()|]
    let f k = spine.[abs(k.GetHashCode()) % spine.Length]
    Seq.iter (fun (k, v) -> (f k).Add (k, v)) xs
    fun k -> Seq.pick (fun (k', v) -> if k=k' then Some v else None) (f k);;
val hashtbl : seq<'a * 'b> -> ('a -> 'b) when 'a : equality
于 2010-05-25T02:14:57.127 に答える
0

上記のコードを使用する可能性がある人は、メモリ リークに注意してください。

tmpNode->key   = (char*)malloc(strlen(key)+1);   //must have +1 for '\0'
tmpNode->value = (char*)malloc(strlen(value)+1); //must have +1
strcpy(tmpNode->key, key);
strcpy(tmpNode->value, value);

コードを完成させるには:

HashNode* AppendLinkedNode(HashNode* ptr, char* key, char* value)
{
    //follow pointer till end
    while (ptr->nextEntry!=NULL)
    {
        if (strcmp(ptr->value,value)==0) return NULL;
        ptr=ptr->nextEntry;
    }
    ptr->nextEntry=newNode(key,value);
    return ptr->nextEntry;
}
于 2009-05-06T06:09:31.990 に答える
-1

ハッシュに関するウィキペディアのページをいくつか読んでみました: http://en.wikipedia.org/wiki/Hash_table。ここにハッシュテーブルのコードを配置するのは大変な作業のように思えます。特に、私が使用するほとんどの言語にはすでにハッシュテーブルが組み込まれているためです。なぜここに実装が必要なのですか? これは本当に言語ライブラリに属しています。

予想されるソリューションに含める必要があるものについて詳しく説明してください。

  • ハッシュ関数
  • 可変バケット数
  • 衝突挙動

また、ここでそれらを収集する目的が何であるかを述べてください。深刻な実装は簡単に口いっぱいになります = これは非常に長い回答につながります (それぞれ数ページの長さになる可能性があります)。また、ライブラリからコードをコピーするよう人々を誘惑している可能性もあります...

于 2008-08-24T19:38:00.397 に答える