Что означает «хеш-таблица открыта» в Java?

Question

Я читал Java api docs в классе Hashtable и наткнулся на несколько вопросов. В документ, он говорит: "Note that the hash table is open: in the case of a "hash collision", a single bucket stores multiple entries, which must be searched sequentially." Я попытался следующий код сам

Hashtable<String, Integer> me = new Hashtable<String, Integer>(); 
me.put("one", new Integer(1)); 
me.put("two", new Integer(2)); 
me.put("two", new Integer(3)); 
System.out.println(me.get("one")); 
System.out.println(me.get("two")); 

из положить был

1 
3 

1. Является ли это то, что он подразумевает под "открытым"?
2. Что случилось с Integer 2? собранный как мусор?
3. Есть ли «закрытый» пример?

Answer 1

Нет, это не то, что подразумевается под «открытым».

Обратите внимание на разницу между ключом и хеш столкновение.

В Hashtable не допускается использование более одной записи с тем же ключом (как в вашем примере вы помещаете две записи с ключом «два», второй (3) заменяет первый (2), и у вас остался только второй в Hashtable).

A hash столкновение - это когда два разных ключа имеют один и тот же хэш-код (возвращенный их методом hashCode()). Различные реализации хеш-таблиц могут относиться к этому по-разному, в основном с точки зрения реализации на низком уровне. Будучи «открытым», Hashtable будет хранить связанный список записей, чьи хэши ключей имеют одинаковое значение. Это может привести в худшем случае к производительности O (N) для простых операций, которые обычно были бы O (1) в хэш-карте, где хэши в основном были разными значениями.

Answer 2

Хэш - это вычисленная функция, которая отображает один объект («один» или «два» в вашем примере) в (целое). Это означает, что могут быть несколько значений, которые сопоставляются с одним и тем же целым числом (целое число имеет конечное число допустимых значений, тогда как может быть бесконечное количество входов). В этом случае «равный» должен быть способен рассказать обо всех этих двух. Таким образом, ваш пример кода правильный, но может быть и другой ключ, который имеет тот же хэш-код (и будет помещен в то же самое ведро, что и «два»).

Answer 3

Это означает, что Hashtable использует open hashing (также известный как отдельная цепочка) для борьбы с хеш-столкновениями. Если две отдельные клавиши имеют один и тот же хэш-код, оба они будут сохранены в одном и том же ведре (в списке).

Answer 4

Открыть означает, что если два ключа не равны, но имеют одинаковое значение хеширования, они будут храниться в одном и том же «ведре». В этом случае вы можете думать о каждом ведре как о связанном списке, поэтому, если многие вещи хранятся в одном и том же ковше, производительность поиска будет уменьшаться.

Ковш 0: Ничего
Ковш 1: Пункт 1
Bucket 2: Пункт 2 -> Пункт 3
Ковш 3: Ничего
Ковш 4: Пункт

В этом случае, если вы найдите ключ, содержащий хеши в bucket 2, затем вы должны выполнить поиск O (n) в списке, чтобы найти ключ, равный тому, что вы ищете.Если ключевые хэши в Bucket 0, 1, 3 или 4, то вы получаете производительность поиска O (1).

Answer 5

Это означает, что два элемента с различными ключами, которые имеют же Hashcode конец вверх в же ведро.

В вашем случае клавиши «два» являются одинаковыми, и поэтому второй поместит первый символ.

Но если предположить, что у вас есть свой собственный класс

class Thingy { 
    private final String name; 

    public Thingy(String name) { 
     this.name = name; 
    } 

    public boolean equals(Object o) { 
     ... 

    } 

    public int hashcode() { 
     //not the worlds best idea 
     return 1; 
    } 

} 

И создал несколько экземпляров. т.е.

Thingy a = new Thingy("a"); 
Thingy b = new Thingy("b"); 
Thingy c = new Thingy("c"); 

И вставил их в карту. Затем один ведро, то есть ведро, содержащее материал с хэш-кодом 1, будет содержать список (цепочку) трех элементов.

Map<Thingy, Thingy> map = new HashMap<Thingy, Thingy>(); 
map.put(a, a); 
map.put(b, b); 
map.put(c, c); 

Так получить деталь любого ключа штуковины приведет к поиску в Hashcode O (1) с последующим линейным поиском O (N) в списке элементов в ведре с хэш-кодом 1.

Также следите за тем, чтобы вы соблюдали правильные отношения при реализации hashcode и equals. А именно, если два объекта равны, то они должны иметь один и тот же код, но необязательно в противном случае, поскольку несколько ключей могут получить один и тот же хэш-код.

Ну и для полного определения открытого хеширования и закрытых хэш-таблиц смотрите здесь http://www.c2.com/cgi/wiki?HashTable

Answer 6

Предупреждение: есть противоречивые определения «открытого хеширования» в обиходе:

Цитирование из http://www.c2.com/cgi/wiki?HashTable процитировано в другом ответе:

Предостережение: некоторые люди используют термин «открытое хеширование» что у меня называется «закрытое хеширование» здесь! использования здесь в соответствии с тем, что в TheArtOfComputerProgramming и IntroductionToAlgorithms, оба которые рекомендуются ссылки, если вы хотите узнать больше о хэш таблицы.

Например, выше страница определяет «открытое хеширование» следующим образом:

Есть две основные стратегии. Open хэширования, которая также называется открытой адресации, говорит: когда запись таблицы вам нужно для новой пары ключ/значение уже заняты, найти другую неиспользуемую запись каким-то образом и поместить его туда.Закрытый хеширование говорит: каждая запись в таблице является вторичной структурой данных (обычно связанный список, но есть и другие возможности ), содержащие фактические данные , и эта структура данных может быть расширена без ограничений.

В противоположность этому, определение поставляется Wikipedia является:

В стратегии, известной как отдельный сцепления, прямого сцепления, или просто цепочки, каждый слот массива ведро является указателем связанный список , содержащий пары ключ-значение, которые хэшируются в том же месте. Поиск требует сканирования списка для записи с заданным ключом. Вставка требует добавления новой записи записи в любой конец списка в хеш-слот . Для удаления требуется для поиска в списке и удаления элемента . (методики также называется открытого хеширования или закрытая адресацией, , который не следует путать с «открытой адресации» или "закрыто хэширования.)

Если так называемые«эксперты»не могут прийти к согласию что означает термин «открытое хеширование», лучше избегать его использования.