Является ли корзина одной ячейкой памяти или похожа на массив ячеек памяти?

Question

Как, например, когда мы говорим, что для двух неравных объектов, имеющих одинаковый хэш-код, объекты хранятся в одном и том же сегменте, что это означает практически?

Answer 1

2 неравных объекта, имеющих одинаковый хеш-код, объекты хранятся в одной корзине, что это означает практически?

Я объясню вам эту концепцию ниже Product пример класса:

Класс продукта:

public class Product {

     private int id;

     public Product(int id) {
        this.id = id;
     }

     //add getters and settes for id

     public boolean equals(Object obj) {
         Product product = (Product)obj;
         if(id == product.getId()) {
             return true;
         }
         return false;
     }

     public int hashcode() {
         return 1;
     }
}

Тестовый класс:

public class Test {

    public static void main(String[] args) {
        Set<Product> set = new HashSet<>();
        Product p1 = new Product(1);
        Product p2 = new Product(2);
        set.add(p1);
        set.add(p2);
    }
}

Предположим, что вы создали два объекта p1 а также p2 за Product класс и добавлен в HashSet как показано выше.

Согласно договору Product учебный класс, p1 а также p2 объекты НЕ равны, потому что их идентификаторы продукта разные. Внутри HashSet эти p1 а также p2 объекты хранятся в разных сегментах (просто помещаются в разные области памяти) в соответствии с hashcode вернулся Product объекты. Потому что оба ваших p1 а также p2 объекты возвращают один и тот же хэш-код (из hashcode() метод из Product класс), они оба будут сохранены в одном ведре (ячейка памяти). Точно так же все ваши product объекты (хотя product объекты не равны) будут помещены в ту же корзину, что и их хэш-код.

Итак, когда вы пытаетесь найти product объект из HashSet используя set.contains() объект должен быть просканирован и найден по всем продуктам (представьте, что вы сохранили 10000 объектов).

Но когда вы реализуете свой hashcode() то есть, возвращая разные хеш-коды для неравных Product объекты, то product объекты будут распределены по разным корзинам, и поиск станет быстрее (не нужно сканировать все объекты), т. е. значительно повысит производительность.

Та же концепция применима для всех Hash * связанные методы коллекции API (HashMap, HashSet и т. д.) в Java.

Является ли корзина одной ячейкой памяти или похожа на массив ячеек памяти?

One Bucket хранит несколько ссылок на объекты, и каждая корзина Hash внутренне использует такие структуры данных, как LinkedList или же TreeMap найти хранимые объекты.

Вы можете посмотреть здесь более подробную информацию на эту тему.

Answer 2

Когда несколько объектов попадают в одно и то же ведро, они сохраняются в виде односвязного списка в этом ведре.

Преимущество хеш-таблицы заключается в том, что вы можете вычислить, к какому сегменту относится ключ, за O(1) раз. Это означает, что если в каждом сегменте содержится только один элемент, ваше время поиска остается неизменным независимо от количества элементов в таблице. Когда у вас есть несколько ключей в одном ведре, вы не можете определить, какой из них вы ищете, не проверяя каждый из них. Когда у вас плохая хеш-функция, которая помещает много элементов в одну корзину, вы теряете преимущество хеш-таблицы, и она начинает вести себя больше как связанный список.