Файл: Import java util. ArrayList public class MyHashMap.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.11.2023
Просмотров: 52
Скачиваний: 3
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
import java.util.ArrayList;public class MyHashMap { private int bucketSize; private ArrayList> buckets; 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 entry = buckets.get(index); 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 entry = buckets.get(index); 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 next; 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 getNext() { return next; } public void setNext(Entry next) { 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), которые хранятся внутри каждого элемента массива. Когда мы ищем значение по ключу, мы сначала хэшируем ключ, чтобы определить, в каком массиве оно находится, а затем ищем в соответствующей цепочке связанных списков. Когда мы удаляем значение по ключу, мы сначала находим его в цепочке связанных списков, а затем удаляем его из цепочки.
Классическая реализация 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), которые хранятся внутри каждого элемента массива. Когда мы ищем значение по ключу, мы сначала хэшируем ключ, чтобы определить, в каком массиве оно находится, а затем ищем в соответствующей цепочке связанных списков. Когда мы удаляем значение по ключу, мы сначала находим его в цепочке связанных списков, а затем удаляем его из цепочки.