Tabela Hash

Neste tutorial, você aprenderá o que é uma tabela de hash. Além disso, você encontrará exemplos funcionais de operações de tabela de hash em C, C ++, Java e Python.

A tabela de hash é uma estrutura de dados que representa os dados na forma de pares de valores-chave . Cada chave é mapeada para um valor na tabela hash. As chaves são usadas para indexar os valores / dados. Uma abordagem semelhante é aplicada por uma matriz associativa.

Os dados são representados em um par de valores-chave com a ajuda de chaves, conforme mostrado na figura abaixo. Cada dado está associado a uma chave. A chave é um número inteiro que aponta para os dados.

1. Tabela de endereço direto

A tabela de endereço direto é usada quando a quantidade de espaço usada pela tabela não é um problema para o programa. Aqui, assumimos que

  • as chaves são pequenos inteiros
  • o número de chaves não é muito grande e
  • não há dois dados com a mesma chave

Um pool de inteiros é chamado de universo U = (0, 1,… ., n-1).
Cada slot de uma tabela de endereço direto T(0… n-1)contém um ponteiro para o elemento que corresponde aos dados.
O índice do array Té a própria chave e o conteúdo Té um ponteiro para o conjunto (key, element). Se não houver nenhum elemento para uma chave, ela será deixada como NULL.

Às vezes, a chave em si são os dados.

Pseudocódigo para operações

 directAddressSearch(T, k) return T(k) directAddressInsert(T, x) T(x.key) = x directAddressDelete(T, x) T(x.key) = NIL

Limitações de uma tabela de endereço direto

  • O valor da chave deve ser pequeno.
  • O número de chaves deve ser pequeno o suficiente para não ultrapassar o limite de tamanho de uma matriz.

2. Tabela de hash

Em uma tabela hash, as chaves são processadas para produzir um novo índice que mapeia para o elemento necessário. Esse processo é chamado de hashing.

Deixe h(x)ser uma função hash e kuma chave.
h(k)é calculado e é usado como um índice para o elemento.

Limitações de uma tabela de hash

  • Se o mesmo índice for produzido pela função hash para várias chaves, surge um conflito. Essa situação é chamada de colisão.
    Para evitar isso, uma função hash adequada é escolhida. Porém, é impossível produzir todas as chaves exclusivas porque |U|>m. Portanto, uma boa função hash pode não evitar as colisões completamente, mas pode reduzir o número de colisões.

No entanto, temos outras técnicas para resolver a colisão.

Vantagens da tabela de hash sobre a tabela de endereço direto:

Os principais problemas com a tabela de endereço direto são o tamanho da matriz e o valor possivelmente grande de uma chave. A função hash reduz o intervalo do índice e, portanto, o tamanho da matriz também é reduzido.
Por exemplo, If k = 9845648451321, then h(k) = 11(usando alguma função hash). Isso ajuda a economizar a memória desperdiçada ao fornecer o índice de 9845648451321para a matriz

Resolução de colisão por encadeamento

Nessa técnica, se uma função hash produz o mesmo índice para vários elementos, esses elementos são armazenados no mesmo índice usando uma lista duplamente vinculada.

Se jfor o slot para vários elementos, ele contém um ponteiro para o início da lista de elementos. Se nenhum elemento estiver presente, jcontém NIL.

Pseudocódigo para operações

 chainedHashSearch(T, k) return T(h(k)) chainedHashInsert(T, x) T(h(x.key)) = x //insert at the head chainedHashDelete(T, x) T(h(x.key)) = NIL

Implementação Python, Java, C e C ++

Python Java C C ++ 
 # Python program to demonstrate working of HashTable hashTable = ((),) * 10 def checkPrime(n): if n == 1 or n == 0: return 0 for i in range(2, n//2): if n % i == 0: return 0 return 1 def getPrime(n): if n % 2 == 0: n = n + 1 while not checkPrime(n): n += 2 return n def hashFunction(key): capacity = getPrime(10) return key % capacity def insertData(key, data): index = hashFunction(key) hashTable(index) = (key, data) def removeData(key): index = hashFunction(key) hashTable(index) = 0 insertData(123, "apple") insertData(432, "mango") insertData(213, "banana") insertData(654, "guava") print(hashTable) removeData(123) print(hashTable) 
 // Java program to demonstrate working of HashTable import java.util.*; class HashTable ( public static void main(String args()) ( Hashtable ht = new Hashtable(); ht.put(123, 432); ht.put(12, 2345); ht.put(15, 5643); ht.put(3, 321); ht.remove(12); System.out.println(ht); ) ) 
 // Implementing hash table in C #include #include struct set ( int key; int data; ); struct set *array; int capacity = 10; int size = 0; int hashFunction(int key) ( return (key % capacity); ) int checkPrime(int n) ( int i; if (n == 1 || n == 0) ( return 0; ) for (i = 2; i < n / 2; i++) ( if (n % i == 0) ( return 0; ) ) return 1; ) int getPrime(int n) ( if (n % 2 == 0) ( n++; ) while (!checkPrime(n)) ( n += 2; ) return n; ) void init_array() ( capacity = getPrime(capacity); array = (struct set *)malloc(capacity * sizeof(struct set)); for (int i = 0; i < capacity; i++) ( array(i).key = 0; array(i).data = 0; ) ) void insert(int key, int data) ( int index = hashFunction(key); if (array(index).data == 0) ( array(index).key = key; array(index).data = data; size++; printf(" Key (%d) has been inserted ", key); ) else if (array(index).key == key) ( array(index).data = data; ) else ( printf(" Collision occured "); ) ) void remove_element(int key) ( int index = hashFunction(key); if (array(index).data == 0) ( printf(" This key does not exist "); ) else ( array(index).key = 0; array(index).data = 0; size--; printf(" Key (%d) has been removed ", key); ) ) void display() ( int i; for (i = 0; i < capacity; i++) ( if (array(i).data == 0) ( printf(" array(%d): / ", i); ) else ( printf(" key: %d array(%d): %d ", array(i).key, i, array(i).data); ) ) ) int size_of_hashtable() ( return size; ) int main() ( int choice, key, data, n; int c = 0; init_array(); do ( printf("1.Insert item in the Hash Table" "2.Remove item from the Hash Table" "3.Check the size of Hash Table" "4.Display a Hash Table" " Please enter your choice: "); scanf("%d", &choice); switch (choice) ( case 1: printf("Enter key -: "); scanf("%d", &key); printf("Enter data -: "); scanf("%d", &data); insert(key, data); break; case 2: printf("Enter the key to delete-:"); scanf("%d", &key); remove_element(key); break; case 3: n = size_of_hashtable(); printf("Size of Hash Table is-:%d", n); break; case 4: display(); break; default: printf("Invalid Input"); ) printf("Do you want to continue (press 1 for yes): "); scanf("%d", &c); ) while (c == 1); )
 // Implementing hash table in C++ #include #include using namespace std; class HashTable ( int capacity; list *table; public: HashTable(int V); void insertItem(int key, int data); void deleteItem(int key); int checkPrime(int n) ( int i; if (n == 1 || n == 0) ( return 0; ) for (i = 2; i  capacity = size; table = new list(capacity); ) void HashTable::insertItem(int key, int data) ( int index = hashFunction(key); table(index).push_back(data); ) void HashTable::deleteItem(int key) ( int index = hashFunction(key); list::iterator i; for (i = table(index).begin(); i != table(index).end(); i++) ( if (*i == key) break; ) if (i != table(index).end()) table(index).erase(i); ) void HashTable::displayHash() ( for (int i = 0; i < capacity; i++) ( cout << "table(" << i << ")"; for (auto x : table(i)) cout < " << x; cout << endl; ) ) int main() ( int key() = (231, 321, 212, 321, 433, 262); int data() = (123, 432, 523, 43, 423, 111); int size = sizeof(key) / sizeof(key(0)); HashTable h(size); for (int i = 0; i < n; i++) h.insertItem(key(i), data(i)); h.deleteItem(12); h.displayHash(); )

Boas funções de hash

Uma boa função hash tem as seguintes características.

  1. Ele não deve gerar chaves muito grandes e o espaço do balde é pequeno. Espaço é desperdiçado.
  2. As chaves geradas não devem estar nem muito próximas nem muito distantes do alcance.
  3. A colisão deve ser minimizada tanto quanto possível.

Alguns dos métodos usados ​​para hashing são:

Método de Divisão

Se kfor uma chave e mfor do tamanho da tabela hash, a função hash h()é calculada como:

h(k) = k mod m

Por exemplo, se o tamanho de uma tabela hash é 10e, em k = 112seguida, h(k) = 112mod 10 = 2. O valor de mnão deve ser os poderes de 2. Isso ocorre porque os poderes do 2em formato binário são 10, 100, 1000,… . Quando encontrarmos k mod m, sempre obteremos os bits-p de ordem inferior.

 if m = 22, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 01 if m = 23, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 001 if m = 24, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 0001 if m = 2p, then h(k) = p lower bits of m

Multiplication Method

h(k) = ⌊m(kA mod 1)⌋
where,

  • kA mod 1 gives the fractional part kA,
  • ⌊ ⌋ gives the floor value
  • A is any constant. The value of A lies between 0 and 1. But, an optimal choice will be ≈ (√5-1)/2 suggested by Knuth.

Universal Hashing

In Universal hashing, the hash function is chosen at random independent of keys.

Open Addressing

Multiple values can be stored in a single slot in a normal hash table.

By using open addressing, each slot is either filled with a single key or left NIL. All the elements are stored in the hash table itself.

Unlike chaining, multiple elements cannot be fit into the same slot.

Open addressing is basically a collision resolving technique. Some of the methods used by open addressing are:

Linear Probing

In linear probing, collision is resolved by checking the next slot.
h(k, i) = (h'(k) + i) mod m
where,

  • i = (0, 1,… .)
  • h'(k) is a new hash function

If a collision occurs at h(k, 0), then h(k, 1) is checked. In this way, the value of i is incremented linearly.
The problem with linear probing is that a cluster of adjacent slots is filled. When inserting a new element, the entire cluster must be traversed. This adds to the time required to perform operations on the hash table.

Quadratic Probing

In quadratic probing, the spacing between the slots is increased (greater than one) by using the following relation.
h(k, i) = (h'(k) + c1i + c2i2) mod m
where,

  • c1e são constantes auxiliares positivas,c2
  • i = (0, 1,… .)

Hashing duplo

Se ocorrer uma colisão após a aplicação de uma função hash h(k), outra função hash é calculada para encontrar o próximo slot.
h(k, i) = (h1(k) + ih2(k)) mod m

Aplicativos de tabela de hash

As tabelas de hash são implementadas onde

  • busca de tempo constante e inserção é necessária
  • aplicações criptográficas
  • a indexação de dados é necessária

Artigos interessantes...