Bạn sẽ triển khai một hashtable bằng ngôn ngữ x như thế nào?

Question

Điểm của câu hỏi này là thu thập danh sách các ví dụ về triển khai có thể bắt đầu bằng các mảng bằng các ngôn ngữ khác nhau. Nó cũng sẽ tốt đẹp nếu ai đó có thể ném vào một cái nhìn tổng quan khá chi tiết về cách họ làm việc, và những gì đang xảy ra với mỗi ví dụ.

Edit:

Tại sao không chỉ cần sử dụng được xây dựng trong hàm băm trong ngôn ngữ cụ thể của bạn?

Bởi vì chúng ta nên biết bảng băm hoạt động như thế nào và có thể triển khai chúng. Điều này có vẻ không phải là một chủ đề siêu quan trọng, nhưng biết cách một trong những cấu trúc dữ liệu được sử dụng nhiều nhất có vẻ khá quan trọng đối với tôi. Nếu điều này là để trở thành wikipedia của lập trình, thì đây là một số loại câu hỏi mà tôi sẽ đến đây cho. Tôi không tìm kiếm một cuốn sách CS được viết ở đây. Tôi có thể kéo Intro to Algorithms ra khỏi kệ và đọc lên chương về bảng băm và lấy loại thông tin đó. Cụ thể hơn, những gì tôi đang tìm kiếm là ví dụ mã. Không chỉ riêng cho tôi, mà còn cho những người khác có thể một ngày nào đó đang tìm kiếm thông tin tương tự và vấp ngã trên trang này.

Cụ thể hơn: Nếu bạn có để triển khai và không thể sử dụng chức năng tích hợp, bạn sẽ làm như thế nào?

Bạn không cần phải đặt mã ở đây. Đặt nó trong pastebin và chỉ cần liên kết nó.

Answer 1

Tôi nghĩ bạn cần cụ thể hơn một chút. Có một số biến thể về hashtables liên quan đến các tùy chọn sau

• Kích thước cố định có thể bắt buộc hoặc động không?
• Loại hàm băm nào được sử dụng?
• Có bất kỳ hạn chế về hiệu suất nào khi có thể thay đổi kích thước hashtable không?

Danh sách có thể tiếp tục và bật. Mỗi ràng buộc này có thể dẫn đến nhiều triển khai bằng bất kỳ ngôn ngữ nào.

Cá nhân, tôi sẽ chỉ sử dụng hàm bắt đầu có sẵn có sẵn trong ngôn ngữ bạn chọn. Lý do duy nhất tôi thậm chí sẽ xem xét việc thực hiện của riêng tôi sẽ là do vấn đề hiệu suất, và thậm chí sau đó rất khó để đánh bại hầu hết các hiện thực hiện có.

Answer 2

Tôi đã đọc và đọc một số trang Wikipedia về băm: http://en.wikipedia.org/wiki/Hash_table. Nó có vẻ như rất nhiều công việc, để đưa ra mã cho một hashtable ở đây, đặc biệt là vì hầu hết các ngôn ngữ tôi sử dụng allready có chúng được xây dựng in Tại sao bạn muốn triển khai ở đây? Công cụ này thực sự thuộc về một thư viện ngôn ngữ.

Xin hãy giải thích về những gì các giải pháp dự kiến ​​của bạn nên bao gồm:

• hàm băm
• biến xô đếm
• va chạm hành vi

Cũng nêu những gì mục đích thu thập chúng ở đây là. Bất kỳ việc thực hiện nghiêm túc nào cũng sẽ dễ dàng là một câu trả lời đầy đủ = điều này sẽ dẫn đến các câu trả lời rất dài (có thể là một vài trang dài).Bạn cũng có thể lôi kéo mọi người sao chép mã từ thư viện ...

Answer 3

HashTable là một khái niệm thực sự đơn giản: đó là mảng trong đó các cặp khóa và giá trị được đặt vào, (như mảng kết hợp) scheme:

Hàm băm băm khóa vào chỉ mục không sử dụng (hy vọng) vào mảng. giá trị sau đó được đặt vào mảng tại chỉ mục cụ thể đó.

Truy xuất dữ liệu rất dễ dàng, vì chỉ mục vào mảng có thể được tính toán thông qua hàm băm, do đó tra cứu là ~ O (1).

Một vấn đề nảy sinh khi một hàm băm maps 2 phím khác nhau để chỉ số tương tự ... có rất nhiều cách xử lý này mà tôi sẽ không chi tiết ở đây ...

bảng Hash là một cách cơ bản của lưu trữ và truy xuất dữ liệu một cách nhanh chóng và được "tích hợp sẵn" trong hầu hết các thư viện ngôn ngữ lập trình.

Answer 4

Bảng băm là cấu trúc dữ liệu cho phép tra cứu các mục trong thời gian không đổi. Nó hoạt động bằng cách băm một giá trị và chuyển đổi giá trị đó thành một offset trong một mảng. Khái niệm về một bảng băm khá dễ hiểu, nhưng việc thực hiện rõ ràng là khó hơn. Tôi không dán toàn bộ bảng băm ở đây, nhưng đây là một số đoạn mã của bảng băm tôi đã tạo trong C cách đây vài tuần ...

Một trong những điều cơ bản của việc tạo bảng băm là có hàm băm tốt . Tôi sử dụng hàm băm djb2 trong bảng băm của tôi:

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

Rồi đến mã thực tế bản thân để tạo và quản lý các thùng trong bảng

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 thấy nút cuối cùng trong danh sách liên kết và gắn thêm một nút mới vào nó.

Mã này sẽ được sử dụng như thế này:

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

Tìm một nút là một đơn giản như:

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

Và được sử dụng như sau:

char* value = FindNode("10"); 

Answer 5

tôi đang tìm kiếm cho việc triển khai bảng băm C hoàn toàn di động và trở nên quan tâm đến cách thực hiện một bản thân mình. Sau khi tìm kiếm xung quanh một chút, tôi đã tìm thấy: Julienne Walker's The Art of Hashing trong đó có một số hướng dẫn tuyệt vời về băm và băm. Việc triển khai chúng phức tạp hơn một chút so với những gì tôi nghĩ nhưng đó là một bài đọc tuyệt vời.

Answer 6

Đối với những người có thể sử dụng đoạn mã trên, lưu ý các rò rỉ bộ nhớ:

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

Và để hoàn thành mã:

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

Answer 7

Đây là mã của tôi cho một bảng Hash, thực hiện trong Java . Bị trục trặc từ nhỏ - các trường khóa và giá trị không giống nhau. Có thể chỉnh sửa điều đó trong tương lai.

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

Answer 8

thực hiện tối thiểu trong F # như một hàm xây dựng một bảng băm từ một chuỗi cho trước cặp khóa-giá trị và trả về một chức năng để tìm kiếm các bảng băm cho giá trị gắn liền với phím đưa ra:

> 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 

Answer 9

thực hiện Một Java trong < 60 Lộc

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