這個問題的關鍵是收集使用不同語言的數組的哈希表實現列表。如果有人能夠詳細瞭解他們的工作方式以及每個示例發生的情況，這也很好。你會如何在語言x中實現散列表？
編輯：
爲什麼不直接使用內置的散列函數在特定的語言？
因爲我們應該知道哈希表如何工作並能夠實現它們。這似乎不是一個超級重要的話題，但知道如何使用最常用的數據結構對我來說似乎非常重要。如果這要成爲編程的維基百科，那麼這些就是我將來到這裏的一些類型的問題。我不想在這裏寫一本CS書。我可以將現成的算法從現成的算法中解放出來，並閱讀關於哈希表的章節並獲取該類型的信息。更具體地說，我正在尋找的是代碼示例。不僅對我來說尤其如此，對於那些也許有一天會在這個頁面上尋找類似信息並且偶然發現的人來說也是如此。
更具體一點：如果你有來實現它們，並且不能使用內置函數，你會怎麼做？
你不需要把代碼放在這裏。把它放在pastebin中，然後連接它。
我認爲你需要更具體一點。關於以下選項，哈希表有幾種變體：
該列表可以繼續。這些約束中的每一個都可能導致以任何語言執行多個實現。
就我個人而言，我只是使用內置的散列表，可用我的語言選擇。我甚至會考慮實施我自己的唯一原因是由於性能問題，即使如此也很難擊敗大多數現有的實現。
我去讀了一些關於散列的維基百科頁面：http://en.wikipedia.org/wiki/Hash_table。看起來好像有很多工作要爲這裏的散列表編寫代碼，特別是因爲我使用的大多數語言都已經內置了它們。爲什麼你要在這裏實現？這些東西真的屬於語言庫。
請你的期望的解決方案應包括詳細說明：
還規定什麼這裏收集他們的目的是什麼。任何嚴肅的實施都會很容易地出現 - 這將導致很長的答案（可能每頁只有幾頁）。您可能也會誘使人們從庫中複製代碼...
HashTable是一個非常簡單的概念：它是一個將鍵和值對放入（如關聯數組）中的數組，計劃：
散列函數將密鑰散列到（希望）未使用的索引到數組中。該值將被放入該特定索引處的數組中。
數據檢索很容易，因爲可以通過哈希函數計算出數組中的索引，因此查找是~O（1）。
一個問題，當一個哈希函數映射2個不同的密鑰相同的指數出現...有處理這個我不會在這裏詳細多種方式...
哈希表是存儲的根本途徑並快速檢索數據，並且幾乎在所有編程語言庫中「內置」。
這與這個問題有什麼關係？ – mayu 2012-06-21 13:39:54
同意這可能不會回答這個問題，並且這個問題可能不是建設性的，但至少我終於明白爲什麼哈希表很快檢索值！非常尷尬，直到現在我還以爲這是巫術。 – 2015-01-05 08:32:49
散列表數據結構，允許在恆定時間內查找項目。它通過散列值並將該值轉換爲數組中的偏移量來工作。哈希表的概念很容易理解，但實現起來顯然比較困難。我沒有在這裏粘貼整個哈希表，但這裏有幾個星期前我在C做的哈希表的片段...
創建哈希表的基礎之一是有一個很好的散列函數。我在哈希表中使用的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");
我不確定你可以使用`char * value = FindNode（「10」）;`因爲`FindNode`返回`HashTable *`。所以你可能會看到以下幾行： `char * value = FindNode（「10」） - > value;` – 2014-01-17 05:25:31
我一直在尋找爲一個完全可移植的C哈希表實現，並對如何實現自己的一個感興趣。在搜索了一下後，我發現： Julienne Walker's The Art of Hashing它有一些關於散列表和散列表的很棒的教程。實施它們比我想象的要複雜一點，但它是一個很棒的閱讀。
對於那些誰可以使用上面的代碼，請注意內存泄漏：
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;
}
這裏是我的一個哈希表的代碼，在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;
}
}
}
}
在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
上面代碼片段的第3行需要修復：`k.GetHashCode ）`可能返回一個負數（例如，``帶有負散列碼的密鑰'.GetHashCode（）`返回-648767821），這反過來會導致System.IndexOutOfRangeException在通過函數f計算這樣的密鑰的桶號時。 – 2011-09-02 11:16:29
在< 60控制線
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));
}
}
}
Java實現的想法是那麼爲*有機*成爲編程的維基百科。不要強迫問題;這種業力養殖的氣味。 – xanadont 2009-07-18 14:36:41