Подтвердить что ты не робот

Как реализовать хэш-таблицу в языке x?

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

Изменить:

Почему бы просто не использовать встроенные хэш-функции на вашем конкретном языке?

Потому что мы должны знать, как работают хеш-таблицы и быть в состоянии их реализовать. Это может показаться не очень важной темой, но знание того, как работает одна из наиболее используемых структур данных, кажется мне очень важным. Если это станет википедией программирования, то это некоторые из типов вопросов, к которым я приду сюда. Я не ищу книгу CS, которая будет написана здесь. Я мог бы перейти Intro к алгоритмам с полки и прочитать в главе о хэш-таблицах и получить этот тип информации. Более конкретно, что я ищу, это примеры кода. Не только для меня, в частности, но и для других, которые, возможно, когда-нибудь будут искать подобную информацию и спотыкаться по этой странице.

Чтобы быть более конкретным: если вы имели для их реализации и не могли использовать встроенные функции, как бы вы это сделали?

Вам не нужно вводить код здесь. Поместите его в пастебин и просто соедините его.

4b9b3361

ОТВЕТЫ

Ответ 1

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

Код будет использоваться следующим образом:

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

Поиск node прост как:

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

Ответ 2

Реализация Java в < 60 LoC

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

Ответ 3

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

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

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

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

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

Ответ 4

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

Ответ 5

Вот мой код для Hash Table, реализованный на 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;
            }
        }
    }
}

Ответ 6

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

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

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

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

Ответ 7

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

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

Ответ 8

Минимальная реализация в 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

Ответ 9

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

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

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

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