Файл: Import java util. ArrayList public class MyHashMap.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.11.2023
Просмотров: 15
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
import java.util.ArrayList;
public class MyHashMap
private int bucketSize;
private ArrayList
public MyHashMap() {
this.bucketSize = 16;
this.buckets = new ArrayList<>(bucketSize);
for (int i = 0; i < bucketSize; i++) {
buckets.add(null);
}
}
public void put(K key, V value) {
int hash = key.hashCode();
int index = hash % bucketSize;
Entry
while (entry != null && !entry.getKey().equals(key)) {
entry = entry.getNext();
}
if (entry == null) {
entry = new Entry<>(key, value);
buckets.set(index, entry);
} else {
entry.setValue(value);
}
}
public V get(K key) {
int hash = key.hashCode();
int index = hash % bucketSize;
Entry
while (entry != null && !entry.getKey().equals(key)) {
entry = entry.getNext();
}
if (entry == null) {
return null;
} else {
return entry.getValue();
}
}
private static class Entry
private K key;
private V value;
private Entry
public Entry(K key, V value) {
this.key = key;
this.value = value;
next = null;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public Entry
return next;
}
public void setNext(Entry
this.next = next;
}
}
}
Это базовая реализация, которая использует простую хеш-функцию для вычисления индекса бакета для каждого ключа. Каждый бакет представлен списком записей (Entry), чтобы обрабатывать коллизии.
Метод put() использует вычисленный индекс, чтобы получить запись бакета и поискать запись с тем же ключом. Если запись не найдена, создается новая запись и добавляется в бакет. Если запись с ключом уже существует, ее значение обновляется.
Метод get() используется для получения значения по ключу. Он использует ту же хеш-функцию для вычисления индекса бакета, затем перебирает записи в бакете, пока не найдет запись с тем же ключом или не достигнет конца списка записей. Если запись с ключом найдена, возвращается ее значение, иначе возвращается null.
Классическая реализация HashTable в Java может выглядеть примерно так:
public class HashTable {
private final int TABLE_SIZE = 128;
private Entry[] table;
private class Entry {
String key;
String value;
Entry next;
Entry(String key, String value) {
this.key = key;
this.value = value;
this.next = null;
}
}
public HashTable() {
table = new Entry[TABLE_SIZE];
}
public void put(String key, String value) {
int hash = key.hashCode() % TABLE_SIZE;
if (table[hash] == null) {
table[hash] = new Entry(key, value);
} else {
Entry entry = table[hash];
while (entry.next != null && !entry.key.equals(key)) {
entry = entry.next;
}
if (entry.key.equals(key)) {
entry.value = value;
} else {
entry.next = new Entry(key, value);
}
}
}
public String get(String key) {
int hash = key.hashCode() % TABLE_SIZE;
if (table[hash] == null) {
return null;
} else {
Entry entry = table[hash];
while (entry != null && !entry.key.equals(key)) {
entry = entry.next;
}
if (entry == null) {
return null;
} else {
return entry.value;
}
}
}
public void remove(String key) {
int hash = key.hashCode() % TABLE_SIZE;
if (table[hash] != null) {
if (table[hash].key.equals(key)) {
table[hash] = table[hash].next;
} else {
Entry entry = table[hash];
while (entry.next != null && !entry.next.key.equals(key)) {
entry = entry.next;
}
if (entry.next != null) {
entry.next = entry.next.next;
}
}
}
}
}
В этой реализации мы используем массив Entry'ев для хранения пар ключ-значение. Мы хэшируем ключ, чтобы определить индекс в массиве, куда должно быть помещено значение. Если на этом индексе уже есть значение (это означает коллизию), мы сохраняем значение в цепочку связанных списков (linked list), которые хранятся внутри каждого элемента массива. Когда мы ищем значение по ключу, мы сначала хэшируем ключ, чтобы определить, в каком массиве оно находится, а затем ищем в соответствующей цепочке связанных списков. Когда мы удаляем значение по ключу, мы сначала находим его в цепочке связанных списков, а затем удаляем его из цепочки.