Qual function de hashing o Java usa para implementar a class Hashtable?

A partir do livro CLRS (“Introduction to Algorithms”), existem várias funções de hashing, como mod, multiply, etc.

Qual function de hashing o Java usa para mapear as chaves para os slots?

Eu vi que há uma pergunta aqui Hashing function usada na linguagem Java . Mas isso não responde à pergunta, e acho que a resposta marcada para essa pergunta está errada. Ele diz que o hashCode () permite que você faça sua própria function de hash para o Hashtable, mas acho que está errado.

O inteiro retornado por hashCode () é a chave real para Hashtble, então Hashtable usa uma function hash para hash o hashCode (). O que esta resposta implica é que Java lhe dá uma chance de dar a Hashtable uma function hash, mas não, está errado. hashCode () fornece a chave real, não a function hash.

Então, o que exatamente a function de hashing Java usa?

Quando uma chave é incluída ou solicitada em um HashMap no OpenJDK, o stream de execução é o seguinte:

  1. A chave é transformada em um valor de 32 bits usando o método hashCode() definido pelo desenvolvedor.
  2. O valor de 32 bits é então transformado por uma segunda function hash (da qual a resposta de Andrew contém o código-fonte) em um deslocamento dentro da tabela de hash. Esta segunda function hash é fornecida pela implementação do HashMap e não pode ser substituída pelo desenvolvedor.
  3. A input correspondente da tabela hash contém uma referência a uma linked list ou nula, se a chave ainda não existir na tabela de hash. Se houver colisões (várias chaves com o mesmo deslocamento), as chaves, juntamente com seus valores, serão simplesmente coletadas em uma lista unida.

Se o tamanho da tabela de hash foi escolhido adequadamente alto, o número de colisões será limitado. Assim, uma única pesquisa leva apenas tempo constante, em média. Isso é chamado de tempo constante esperado . No entanto, se um invasor tiver controle sobre as chaves inseridas em uma tabela de hash e conhecer o algoritmo de hash em uso, ele poderá provocar muitas colisões de hash e, portanto, forçar o tempo de pesquisa linear. É por isso que algumas implementações de tabela de hash foram alteradas recentemente para include um elemento random que dificulta que um invasor preveja quais chaves causarão colisões.

Alguma arte ASCII

 key.hashCode() | | 32-bit value | hash table V +------------+ +----------------------+ HashMap.hash() --+ | reference | -> | key1 | value1 | null | | |------------| +----------------------+ | modulo size | null | | = offset |------------| +---------------------+ +--------------> | reference | -> | key2 | value2 | ref | |------------| +---------------------+ | .... | | +----------------+ V +----------------------+ | key3 | value3 | null | +----------------------+ 

De acordo com a origem do hashmap, todo hashCode é hash usando o seguinte método:

  /** * Applies a supplemental hash function to a given hashCode, which * defends against poor quality hash functions. This is critical * because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. Note: Null keys always map to hash 0, thus index 0. */ static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } 

A razão pela qual todo hashCode é hash novamente, é evitar ainda mais uma colisão (veja os comentários acima)

O HashMap também usa um método para determinar o índice de um código hash (já que length é sempre uma potência de 2, você pode usar & em vez de%):

 /** * Returns index for hash code h. */ static int indexFor(int h, int length) { return h & (length-1); } 

O método put parece algo como:

 int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); 

A finalidade de um código hash é fornecer uma representação de inteiro exclusiva para um determinado object. Faz sentido, então, que o método hashCode do Integer simplesmente retorne o valor porque cada valor seria exclusivo para esse object Integer.

O hash em geral é dividido em duas etapas: a. HashCode b. Compressão

Na etapa a. um inteiro correspondente à sua chave é gerado. Isso pode ser modificado por você em Java.

Na etapa b. uma técnica de compactação é aplicada por Java para mapear o inteiro retornado pela etapa a. para um slot no hashmap ou hashtable. Essa técnica de compactação não pode ser alterada.

Eu acho que há alguma confusão sobre o conceito aqui. Uma function hash mapeia uma input de tamanho variável para uma saída de tamanho fixo (o valor de hash). No caso de objects Java, a saída é um inteiro assinado de 32 bits.

A Hashtable do Java usa o valor de hash como um índice em uma matriz onde o object real é armazenado, levando em conta a aritmética do módulo e as colisões. No entanto, isso não é hashing.

A implementação java.util.HashMap realiza algumas trocas de bit adicionais no valor de hash antes da indexação para proteger contra colisões excessivas em alguns casos. É chamado de “hash adicional”, mas não acho que seja um termo correto.

Para colocá-lo de uma forma muito simples, o segundo hashing não é nada, mas encontrar o número de índice da matriz bucket onde o novo par de valores-chave será armazenado. Este mapeamento é feito para obter o número do índice do maior valor int do hashcode da chave obj. Agora, se dois objects chaves desiguais tiverem o mesmo código hash, a colisão acontecerá, pois eles serão mapeados para o mesmo índice de array. Nesse caso, a segunda chave, juntamente com seu valor, será adicionada à linked list. Aqui, o índice da matriz apontará para o último nó adicionado.