Хеширащи ключове в Java

В java, когато използвам низ като ключ за Hashmap, получавам малко по-различен резултат, отколкото когато използвам низа hashcode като ключ в HashMap.

Някакво прозрение?


java hashmap hashtable string-hashing
person user1785771    schedule 03.11.2012    source източник
comment
Може ли да бъдеш по-точен? Покажете някакъв кодов фрагмент, където се сблъсквате с този проблем.   -  person Rohit Jain    schedule 03.11.2012
comment
Защо очаквате различен ключ да даде същите резултати? Няма да стане.   -  person user207421    schedule 04.11.2012

Отговори (5)


arrow_upward
12
arrow_downward

когато използвам низа hashcode като ключ в HashMap.

Вие не трябва да използвате самия хеш код като ключ. Хеш кодовете не са предназначени да бъдат уникални - напълно е разрешено две неравни стойности да имат един и същ хеш код. Трябва да използвате самия низ като ключ. След това картата първо ще сравни хеш кодовете (за да стесни бързо съвпаденията на кандидатите) и след това ще сравни с equals за истинско равенство на низовете.

Разбира се, това предполага, че вашият код наистина е такъв, какъвто го прави въпросът ви, напр.

HashMap<String, String> goodMap = new HashMap<String, String>();
goodMap.put("foo", "bar");

HashMap<Integer, String> badMap = new HashMap<Integer, String>();
badMap.put("foo".hashCode(), "bar");

Ако кодът ви наистина изглежда така, просто използвайте HashMap<String, String> вместо това.

От документите за Object.hashCode() (акцентът е мой):

Общият договор на hashCode е:

  • Всеки път, когато се извиква на един и същи обект повече от веднъж по време на изпълнение на приложение на Java, методът hashCode трябва последователно да връща едно и също цяло число, при условие че не се променя информацията, използвана в сравненията на равни на обекта. Това цяло число не трябва да остава последователно от едно изпълнение на приложение до друго изпълнение на същото приложение.
  • Ако два обекта са равни според метода equals(Object), тогава извикването на метода hashCode за всеки от двата обекта трябва да доведе до един и същ целочислен резултат.
  • Не е задължително, ако два обекта са неравни според метода equals(java.lang.Object), тогава извикването на метода hashCode за всеки от двата обекта трябва да доведе до различни цели числа. Въпреки това, Програмистът трябва да е наясно, че произвеждането на различни цели числа за неравни обекти може да подобри производителността на хеш-таблиците.
person Jon Skeet    schedule 03.11.2012

arrow_upward
3
arrow_downward

Разбира се. Различните низове могат да имат един и същ хешкод, така че ако съхраните два такива низа като ключове в карта, ще имате два записа (тъй като низовете са различни). Като има предвид, че ако използвате техния hashCode като ключ, ще имате само един запис (тъй като техният hashCode е същият).

HashCode не се използва, за да се каже дали два ключа са равни. Използва се само за присвояване на кофа към ключа. След като кофата бъде намерена, всеки ключ, съдържащ се в кофата, се сравнява с новия ключ с равни и ключът се добавя към кофата, ако не може да бъде намерен равен ключ.

person JB Nizet    schedule 03.11.2012
comment
Благодаря на всички за отговорите. Опитвам се да избегна съхраняването на ключа като низ, тъй като ще консумира повече памет! - person user1785771; 03.11.2012
comment
Не правете прибързано това заключение без измерване. Защо ще използва повече памет? Картата не прави копие на ключа. Той просто използва препратка към ключа. - person JB Nizet; 03.11.2012
comment
Знам. Но когато имам над два милиона записа, тогава съхраняването на техните струнни ключове ще има голяма разлика! @JB - person user1785771; 03.11.2012
comment
@user1785771: Те използват повече памет по основателна причина: има повече важни данни от само 32-те бита за хеш код. Ако трябва да съхранявате много низове, вземете много памет. Паметта е евтина; грешките, дължащи се на неправилно използване на хеш карта, могат лесно да бъдат много скъпи. - person Jon Skeet; 03.11.2012

arrow_upward
3
arrow_downward

Проблемът е, че дори два обекта да са различни, това не означава, че техните хешкодове също са различни.

Два различни обекта могат да споделят един и същ хешкод. Така че не трябва да ги имате като HashMap ключ.

Освен това, тъй като хеш кодовете, върнати от метода Object.hashCode(), са от тип int, можете да имате само 2^32 различни стойности. Ето защо ще имате "сблъсъци" в зависимост от алгоритъма за хеширане, за различни обекти.

Накратко: -

!obj.equals(obj1) не гарантира, че obj.hashCode() != obj1.hashCode().

person Rohit Jain    schedule 03.11.2012
comment
Бих използвал !obj.equals(obj1) в последния ред, тъй като това е важната част. - person Jon Skeet; 03.11.2012

arrow_upward
1
arrow_downward

HashCodes може да бъде еднакъв или различен за един и същи низ, така че внимавайте с това. Може би това е причината да получите различен резултат.

Ето още един SO въпрос за него . Вижте приетия отговор на Jon Skeet.

person Atif Imran    schedule 03.11.2012

arrow_upward
0
arrow_downward

Вие можете да използвате хеш кода като ключ само ако хеш функцията е перфектен хеш (вижте напр. GPERF). Докато вашите ключови обекти не се намират в паметта, вие сте прави, че ще пестите памет.

person Floris    schedule 01.02.2014