Как Вы реализовали бы хеш-таблицу на языке x? [закрытый]

Хэш-таблица структура данных, которая позволяет поиск объектов в постоянное время. Это работает путем хеширования значения и преобразования того значения в смещение в массиве. Понятие хэш-таблицы довольно легко понять, но реализация, очевидно, более трудна. Я не вставляю целую хэш-таблицу здесь, но здесь являюсь некоторыми отрывками хэш-таблицы, которую я сделал в 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");

HashTable является действительно простым понятием: это - массив, в который пары ключ/значение помещаются в, (как ассоциативный массив) следующей схемой:

хеш-функция А хеширует ключ к (надо надеяться), неиспользованному индексу в массив. значение тогда помещается в массив в тот конкретный индекс.

Поиск данных легок, поскольку индекс в массив может быть вычислен через хеш-функцию, таким образом искать, ~ O (1).

проблема А возникает, когда хеш-функция отображает 2 различных ключа к тому же индексу... существует много способов обработать это, которое я не детализирую здесь...

Хэш-таблицы являются фундаментальным способом сохранить и получить данные быстро, и "встроены" почти во всех библиотеках языка программирования.

Я искал абсолютно портативную реализацию хэш-таблицы C и заинтересовался тем, как реализовать тот сам. После поиска вокруг немного я нашел: Julienne Walker Искусство Хеширования , который имеет некоторые большие учебные руководства на перемешанных таблицах и хэш-таблицах. Реализация их немного более сложна, чем я думал, но это было большое чтение.

Я думаю, что необходимо быть немного более конкретными. Существует несколько изменений на хеш-таблицах относительно следующих опций

• , фиксированный размер хеш-таблицы или динамичный?
• , Какая хеш-функция используется?
• там какие-либо ограничения производительности, когда хеш-таблица изменена?

список может продолжиться и на. Каждое из этих ограничений могло привести к нескольким реализациям на любом языке.

Лично, я просто использовал бы встроенную хеш-таблицу, которая доступна на моем предпочтительном языке. Единственная причина я даже рассмотрел бы реализацию моего собственного, произойдет из-за проблем производительности, и даже тогда трудно разбить большинство существующих реализаций.

Я пошел, и считайте часть страницы Википедии на хешировании: http://en.wikipedia.org/wiki/Hash_table . Это походит на большую работу, для подъема кода для хеш-таблицы здесь, тем более, что большинству языков, которые я использую уже, встроили их. Почему Вы хотели бы реализации здесь? Этот материал действительно входит в состав библиотеки языков.

уточните то, что должны включать Ваши ожидаемые решения:

• поведение коллизии количества
• блока переменной хеш-функции

Также состояние, что цель собрать их вот. Любая серьезная реализация легко будет настоящим полным ртом =, это приведет к очень длинным ответам (возможно несколько страниц длиной каждый). Вы могли бы также соблазнять людей копировать код с библиотеки...

Для тех, кто может использовать приведенный выше код, обратите внимание на утечку памяти:

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