Implémentation d'une carte à l'aide du hachage
- WBOYoriginal
- 2024-07-28 07:43:13513parcourir
Une carte peut être implémentée en utilisant le hachage. Vous comprenez maintenant le concept de hachage. Vous savez comment concevoir une bonne fonction de hachage pour mapper une clé à un index dans une table de hachage, comment mesurer les performances à l'aide du facteur de charge, et comment augmenter la taille de la table et rehacher pour maintenir les performances. Cette section montre comment implémenter une carte en utilisant un chaînage séparé.
Nous concevons notre interface Map personnalisée pour refléter java.util.Map et nommons l'interface MyMap et une classe concrète MyHashMap , comme le montre la figure ci-dessous.
Comment implémentez-vous MyHashMap ? Si vous utilisez une ArrayList et stockez une nouvelle entrée à la fin de la liste, le temps de recherche sera O(n). Si vous implémentez MyHashMap en utilisant un arbre binaire, le temps de recherche sera O(log n) si l'arbre est bien équilibré. Néanmoins, vous pouvez implémenter MyHashMap en utilisant le hachage pour obtenir un algorithme de recherche temporelle O(1). Le code ci-dessous montre l'interface MyMap.
package demo;
public interface MyMap<K, V> {
/** Remove all of the entries from this map */
public void clear();
/** Return true if the specified key is in the map */
public boolean containsKey(K key);
/** Return true if this map contains the specified value */
public boolean containsValue(V value);
/** Return a set of entries in the map */
public java.util.Set<Entry<K, V>> entrySet();
/** Return the value that matches the specified key */
public V get(K key);
/** Return true if this map doesn't contain any entries */
public boolean isEmpty();
/** Return a set consisting of the keys in this map */
public java.util.Set<K> keySet();
/** Add an entry (key, value) into the map */
public V put(K key, V value);
/** Remove an entry for the specified key */
public void remove(K key);
/** Return the number of mappings in this map */
public int size();
/** Return a set consisting of the values in this map */
public java.util.Set<V> values();
/** Define an inner class for Entry */
public static class Entry<K, V> {
K key;
V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
@Override
public String toString() {
return "[" + key + ", " + value + "]";
}
}
}
Le code ci-dessous implémente MyHashMap en utilisant un chaînage séparé.
package demo;
import java.util.LinkedList;
public class MyHashMap<K, V> implements MyMap<K, V> {
// Define the default hash-table size. Must be a power of 2
private static int DEFAULT_INITIAL_CAPACITY = 4;
// Define the maximum hash-table size. 1 << 30 is same as 2^30
private static int MAXIMUM_CAPACITY = 1 << 30;
// Current hash-table capacity. Capacity is a power of 2
private int capacity;
// Define default load factor
private static float DEFAULT_MAX_LOAD_FACTOR = 0.75f;
// Specify a load factor used in the hash table
private float loadFactorThreshold;
// The number of entries in the map
private int size = 0;
// Hash table is an array with each cell being a linked list
LinkedList<MyMap.Entry<K, V>>[] table;
/** Construct a map with the default capacity and load factor */
public MyHashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR);
}
/** Construct a map with the specified initial capacity and
* default load factor */
public MyHashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR);
}
/** Construct a map with the specified initial capacity
* and load factor */
public MyHashMap(int initialCapacity, float loadFactorThreshold) {
if(initialCapacity > MAXIMUM_CAPACITY)
this.capacity = MAXIMUM_CAPACITY;
else
this.capacity = trimToPowerOf2(initialCapacity);
this.loadFactorThreshold = loadFactorThreshold;
table = new LinkedList[capacity];
}
@Override /** Remove all of the entries from this map */
public void clear() {
size = 0;
removeEntries();
}
@Override /** Return true if the specified key is in the map */
public boolean containsKey(K key) {
if(get(key) != null)
return true;
else
return false;
}
@Override /** Return true if this map contains the value */
public boolean containsValue(V value) {
for(int i = 0; i < capacity; i++) {
if(table[i] != null) {
LinkedList<Entry<K ,V>> bucket = table[i];
for(Entry<K, V> entry: bucket)
if(entry.getValue().equals(value))
return true;
}
}
return false;
}
@Override /** Return a set of entries in the map */
public java.util.Set<MyMap.Entry<K, V>> entrySet() {
java.util.Set<MyMap.Entry<K, V>> set = new java.util.HashSet<>();
for(int i = 0; i < capacity; i++) {
if(table[i] != null) {
LinkedList<Entry<K, V>> bucket = table[i];
for(Entry<K, V> entry: bucket)
set.add(entry);
}
}
return set;
}
@Override /** Return the value that matches the specified key */
public V get(K key) {
int bucketIndex = hash(key.hashCode());
if(table[bucketIndex] != null) {
LinkedList<Entry<K, V>> bucket = table[bucketIndex];
for(Entry<K, V> entry: bucket)
if(entry.getKey().equals(key))
return entry.getValue();
}
return null;
}
@Override /** Return true if this map contains no entries */
public boolean isEmpty() {
return size == 0;
}
@Override /** Return a set consisting of the keys in this map */
public java.util.Set<K> keySet() {
java.util.Set<K> set = new java.util.HashSet<K>();
for(int i = 0; i < capacity; i++) {
if(table[i] != null) {
LinkedList<Entry<K, V>> bucket = table[i];
for(Entry<K, V> entry: bucket)
set.add(entry.getKey());
}
}
return set;
}
@Override /** Add an entry (key, value) into the map */
public V put(K key, V value) {
if(get(key) != null) { // The key is already in the map
int bucketIndex = hash(key.hashCode());
LinkedList<Entry<K, V>> bucket = table[bucketIndex];
for(Entry<K, V> entry: bucket)
if(entry.getKey().equals(key)) {
V oldValue = entry.getValue();
// Replace old value with new value
entry.value = value;
// Return the old value for the key
return oldValue;
}
}
// Check load factor
if(size >= capacity * loadFactorThreshold) {
if(capacity == MAXIMUM_CAPACITY)
throw new RuntimeException("Exceeding maximum capacity");
rehash();
}
int bucketIndex = hash(key.hashCode());
// Create a linked list for the bucket if not already created
if(table[bucketIndex] == null) {
table[bucketIndex] = new LinkedList<Entry<K, V>>();
}
// Add a new entry (key, value) to hashTable[index]
table[bucketIndex].add(new MyMap.Entry<K, V>(key, value));
size++; // Increase size
return value;
}
@Override /** Remove the entries for the specified key */
public void remove(K key) {
int bucketIndex = hash(key.hashCode());
// Remove the first entry that matches the key from a bucket
if(table[bucketIndex] != null) {
LinkedList<Entry<K, V>> bucket = table[bucketIndex];
for(Entry<K, V> entry: bucket)
if(entry.getKey().equals(key)) {
bucket.remove(entry);
size--; // Decrease size
break; // Remove just one entry that matches the key
}
}
}
@Override /** Return the number of entries in this map */
public int size() {
return size;
}
@Override /** Return a set consisting of the values in this map */
public java.util.Set<V> values() {
java.util.Set<V> set = new java.util.HashSet<>();
for(int i = 0; i < capacity; i++) {
if(table[i] != null) {
LinkedList<Entry<K, V>> bucket = table[i];
for(Entry<K, V> entry: bucket)
set.add(entry.getValue());
}
}
return set;
}
/** Hash function */
private int hash(int hashCode) {
return supplementalHash(hashCode) & (capacity - 1);
}
/** Ensure the hashing is evenly distributed */
private static int supplementalHash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/** Return a power of 2 for initialCapacity */
private int trimToPowerOf2(int initialCapacity) {
int capacity = 1;
while(capacity < initialCapacity) {
capacity <<= 1; // Same as capacity *= 2. <= is more efficient
}
return capacity;
}
/** Remove all entries from each bucket */
private void removeEntries() {
for(int i = 0; i < capacity; i++) {
if(table[i] != null) {
table[i].clear();
}
}
}
/** Rehash the map */
private void rehash() {
java.util.Set<Entry<K, V>> set = entrySet(); // Get entries
capacity <<= 1; // Same as capacity *= 2. <= is more efficient
table = new LinkedList[capacity]; // Create a new hash table
size = 0; // Reset size to 0
for(Entry<K, V> entry: set) {
put(entry.getKey(), entry.getValue()); // Store to new table
}
}
@Override /** Return a string representation for this map */
public String toString() {
StringBuilder builder = new StringBuilder("[");
for(int i = 0; i < capacity; i++) {
if(table[i] != null && table[i].size() > 0)
for(Entry<K, V> entry: table[i])
builder.append(entry);
}
builder.append("]");
return builder.toString();
}
}
La classe MyHashMap implémente l'interface MyMap en utilisant un chaînage séparé. Les paramètres qui déterminent la taille de la table de hachage et les facteurs de charge sont définis dans la classe. La capacité initiale par défaut est 4 (ligne 5) et la capacité maximale est de 2^30 (ligne 8). La table de hachage actuelle
la capacité est conçue comme une valeur de la puissance de 2 (ligne 11). Le seuil de facteur de charge par défaut est 0,75f (ligne 14). Vous pouvez spécifier un seuil de facteur de charge personnalisé lors de la création d'une carte. Le seuil de facteur de charge personnalisé est stocké dans loadFactorThreshold (ligne 17). Le champ de données taille indique le nombre d'entrées dans la carte (ligne 20). La table de hachage est un tableau. Chaque cellule du tableau est une liste chaînée (ligne 23).
Trois constructeurs sont fournis pour construire une carte. Vous pouvez créer une carte par défaut avec la capacité et le seuil de facteur de charge par défaut à l'aide du constructeur sans argument (lignes 26 à 28), une carte avec la capacité spécifiée et un seuil de facteur de charge par défaut (lignes 32 à 34) et un carte avec la capacité spécifiée et le seuil de facteur de charge (lignes 38 à 46).
La méthode clear supprime toutes les entrées de la carte (lignes 49 à 52). Il appelle removeEntries(), qui supprime toutes les entrées dans les compartiments (lignes 221 à 227). La méthode removeEntries() prend un temps O(capacity) pour effacer toutes les entrées du tableau.
La méthode containsKey(key) vérifie si la clé spécifiée est dans la carte en appelant la méthode get (lignes 55 à 60). Puisque la méthode get prend un temps O(1), la méthode containsKey(key) prend un temps O(1).
La méthode containsValue(value) vérifie si la valeur est dans la carte (lignes 63 à 74). Cette méthode prend un temps O(capacité + taille). Il s'agit en fait de O (capacité), puisque la capacité est de taille 7.
La méthode entrySet() renvoie un ensemble qui contient toutes les entrées de la carte (lignes 77 à 90). Cette méthode prend un temps O(capacité).
La méthode get(key) renvoie la valeur de la première entrée avec la clé spécifiée (lignes 93 à 103). Cette méthode prend un temps O(1).
La méthode isEmpty() renvoie simplement true si la carte est vide (lignes 106 à 108). Cette méthode prend un temps O(1).
La méthode keySet() renvoie toutes les clés de la carte sous forme d'un ensemble. La méthode recherche les clés de chaque compartiment et les ajoute à un ensemble (lignes 111 à 123). Cette méthode prend un temps O(capacité).
La méthode put(key, value) ajoute une nouvelle entrée dans la carte. La méthode teste d'abord si la clé est déjà dans la carte (ligne 127), si c'est le cas, elle localise l'entrée et remplace l'ancienne valeur par la nouvelle valeur dans l'entrée de la clé (ligne 134) et l'ancienne valeur est renvoyée ( ligne 136). Si la clé est nouvelle dans la carte, la nouvelle entrée est créée dans la carte (ligne 156). Avant d'insérer la nouvelle entrée, la méthode vérifie si la taille dépasse le seuil du facteur de charge (ligne 141). Si tel est le cas, le programme appelle rehash() (ligne 145) pour augmenter la capacité et stocker les entrées dans la nouvelle table de hachage plus grande.
La méthode rehash() copie d'abord toutes les entrées d'un ensemble (ligne 231), double la capacité (ligne 232), crée une nouvelle table de hachage (ligne 233) et réinitialise la taille à 0 (ligne 234). La méthode copie ensuite les entrées dans la nouvelle table de hachage (lignes 236 à 238). La méthode rehash prend un temps O(capacité). Si aucune répétition n'est effectuée, la méthode put prend un temps O(1) pour ajouter une nouvelle entrée.
La méthode remove(key) supprime l'entrée avec la clé spécifiée dans la carte (lignes 164 à 177). Cette méthode prend un temps O(1).
La méthode size() renvoie simplement la taille de la carte (lignes 180 à 182). Cette méthode prend un temps O(1).
La méthode values() renvoie toutes les valeurs de la carte. La méthode examine chaque entrée de tous les compartiments et l'ajoute à un ensemble (lignes 185 à 197). Cette méthode prend un temps O(capacité).
La méthode hash() appelle le supplementalHash pour garantir que le hachage est uniformément réparti afin de produire un index pour la table de hachage (lignes 200 à 208). Cette méthode prend un temps O(1).
Le tableau ci-dessous résume les complexités temporelles des méthodes dans MyHashMap.
Comme le rehachage n'arrive pas très souvent, la complexité temporelle de la méthode put est O(1). Notez que la complexité des méthodes clear, entrySet, keySet, values et rehash dépendent de capacité, donc pour éviter de mauvaises performances pour ces méthodes, vous devez choisir soigneusement une capacité initiale.
Le code ci-dessous donne un programme de test qui utilise MyHashMap.
Le programme crée une carte en utilisant MyHashMap (ligne 7) et ajoute cinq entrées dans la carte (lignes 8 à 12). La ligne 5 ajoute la clé Smith avec la valeur 30 et la ligne 9 ajoute Smith avec la valeur 65. Cette dernière valeur remplace l'ancienne valeur. La carte ne comporte en réalité que quatre entrées. Le programme affiche les entrées dans la carte (ligne 14), obtient une valeur pour une clé (ligne 16), vérifie si la carte contient la clé (ligne 18) et une valeur (ligne 19), supprime une entrée avec la clé Smith (ligne 21), et réaffiche les entrées dans la carte (ligne 22). Enfin, le programme efface la carte (ligne 24) et affiche une carte vide (ligne 25).
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!