HashMap에서 문자열 키를 사용하는 것이 좋지 않습니까?

HashMap에서 문자열 키를 사용하는 것이 좋지 않습니까?

---

String 클래스의 hashCode () 메서드가 고유 한 String-s에 대해 고유 한 해시 코드를 생성하도록 보장 되지 않는다는 것을 이해합니다 . String 키를 HashMap-s에 넣는 많은 사용법을 봅니다 (기본 String hashCode () 메서드 사용). 이러한 사용으로 인해 맵 put이 이전에 완전히 구별되는 String 키를 사용 하여 맵에 배치 된 HashMap 항목을 대체 한 경우 심각한 애플리케이션 문제가 발생할 수 있습니다 .

String.hashCode ()가 고유 한 String-s에 대해 동일한 값을 반환하는 시나리오에서 실행할 확률은 얼마입니까? 키가 문자열 인 경우 개발자는이 문제를 어떻게 해결합니까?

---

개발자는 프로그램 정확성을 달성하기 위해 HashMap의 해시 충돌 문제를 해결할 필요가 없습니다.

여기에서 이해해야 할 몇 가지 핵심 사항이 있습니다.

1. 충돌은 해싱의 고유 한 기능이며 반드시 그래야합니다. 가능한 값의 수 (귀하의 경우 문자열이지만 다른 유형에도 적용됨)는 정수 범위보다 훨씬 큽니다.

2. 해싱의 모든 사용에는 충돌을 처리하는 방법이 있으며 Java 컬렉션 (HashMap 포함)도 예외는 아닙니다.

3. 해싱은 동등성 테스트에 관여하지 않습니다. 동일한 객체가 동일한 해시 코드를 가져야한다는 것은 사실이지만 그 반대는 사실이 아닙니다. 많은 값이 동일한 해시 코드를 갖게됩니다. 따라서 평등을 대신하여 해시 코드 비교를 사용하지 마십시오. 컬렉션은 그렇지 않습니다. 그들은 해싱을 사용하여 하위 컬렉션 (Java 컬렉션 세계에서는 버킷이라고 함)을 선택하지만 .equals ()를 사용하여 실제로 동등성을 확인합니다.

4. 컬렉션에서 잘못된 결과를 유발하는 충돌에 대해 걱정할 필요가 없을뿐만 아니라 대부분의 응용 프로그램에서 * 일반적으로 * 성능에 대해 걱정할 필요가 없습니다. Java 해시 컬렉션은 해시 코드를 관리하는 데 매우 효과적입니다.

5. 더 좋은 점은 (Strings as keys)에 대해 질문 한 경우 Java의 String 클래스가 꽤 좋은 해시 코드를 생성하기 때문에 해시 코드 자체에 대해 걱정할 필요가 없습니다. 따라서 제공된 Java 클래스의 대부분을 수행하십시오.

원하는 경우 더 자세한 정보 :

해싱이 작동하는 방식 (특히, Java의 HashMap과 같은 해시 컬렉션의 경우)은 다음과 같습니다.

• HashMap은 버킷이라고하는 하위 컬렉션 컬렉션에 제공 한 값을 저장합니다. 이들은 실제로 연결 목록으로 구현됩니다. iirc, 기본적으로 시작하는 16, 맵에 더 많은 항목을 넣을수록 숫자가 늘어납니다. 항상 값보다 더 많은 버킷이 있어야합니다. 한 가지 예를 제공하기 위해 기본값을 사용하여 HashMap에 100 개의 항목을 추가하면 256 개의 버킷이 있습니다.

• 맵에서 키로 사용할 수있는 모든 값은 해시 코드라고하는 정수 값을 생성 할 수 있어야합니다.

• HashMap은이 해시 코드를 사용하여 버킷을 선택합니다. 궁극적으로 이것은 정수 값 modulo을 버킷 수로 가져 오는 것을 의미 하지만 그 전에 Java의 HashMap에는 hash()알려진 일부 클 럼핑 소스를 줄이기 위해 해시 코드를 조정 하는 내부 메소드 (라고 함 )가 있습니다.

• 값을 찾을 때 HashMap은 버킷을 선택한 다음를 사용하여 연결된 목록의 선형 검색을 통해 개별 요소를 검색합니다 .equals().

따라서 정확성을 위해 충돌을 해결할 필요가 없으며 일반적으로 성능에 대해 걱정할 필요가 없으며 기본 Java 클래스 (예 : String)를 사용하는 경우 걱정할 필요가 없습니다. 해시 코드 값을 생성합니다.

고유 한 해시 코드 메서드를 작성해야하는 경우 (즉, 이름 / 성 쌍과 같은 복합 값이있는 클래스를 작성했음을 의미 함) 상황이 약간 더 복잡해집니다. 여기서 틀릴 가능성이 있지만 로켓 과학은 아닙니다. 먼저, 이것을 아십시오. 정확성을 보장하기 위해해야 ​​할 유일한 일은 동일한 객체가 동일한 해시 코드를 생성하도록하는 것입니다. 따라서 클래스에 대한 hashcode () 메서드를 작성하는 경우 equals () 메서드도 작성해야하며 각 메서드에서 동일한 값을 검사해야합니다.

나쁘지만 올바른 hashcode () 메서드를 작성할 수 있습니다. 즉, "동일한 객체는 동일한 해시 코드를 생성해야합니다"제약 조건을 충족하지만 충돌이 많기 때문에 성능이 매우 저하됩니다.

이것의 표준 퇴화 최악의 경우는 모든 경우에 대해 상수 값 (예 : 3)을 단순히 반환하는 메서드를 작성하는 것입니다. 이는 모든 값이 동일한 버킷으로 해시된다는 것을 의미합니다.

여전히 작동 하지만 성능이 연결된 목록의 성능으로 저하됩니다.

분명히 그런 끔찍한 hashcode () 메서드를 작성하지 않을 것입니다. 괜찮은 IDE를 사용하는 경우 하나를 생성 할 수 있습니다. StackOverflow는 코드를 좋아하기 때문에 위의 이름 / 성 클래스에 대한 코드는 다음과 같습니다.

public class SimpleName {
    private String firstName;
    private String lastName;
    public SimpleName(String firstName, String lastName) {
        super();
        this.firstName = firstName;
        this.lastName = lastName;
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result
                + ((firstName == null) ? 0 : firstName.hashCode());
        result = prime * result
                + ((lastName == null) ? 0 : lastName.hashCode());
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        SimpleName other = (SimpleName) obj;
        if (firstName == null) {
            if (other.firstName != null)
                return false;
        } else if (!firstName.equals(other.firstName))
            return false;
        if (lastName == null) {
            if (other.lastName != null)
                return false;
        } else if (!lastName.equals(other.lastName))
            return false;
        return true;
    }
}

---

나는 그 HashMap.put방법이 단지 String.hashCode.

There is definitely going to be a chance of a hash collision, so one would expect that the String.equals method will also be called to be sure that the Strings are truly equal, if there is indeed a case where the two Strings have the same value returned from hashCode.

Therefore, the new key String would only be judged to be the same key String as one that is already in the HashMap if and only if the value returned by hashCode is equal, and the equals method returns true.

Also to add, this thought would also be true for classes other than String, as the Object class itself already has the hashCode and equals methods.

Edit

So, to answer the question, no, it would not be a bad idea to use a String for a key to a HashMap.

---

This is not an issue, it's just how hashtables work. It's provably impossible to have distinct hashcodes for all distinct strings, because there are far more distinct strings than integers.

As others have written, hash collisions are resolved via the equals() method. The only problem this can cause is degeneration of the hashtable, leading to bad performance. That's why Java's HashMap has a load factor, a ratio between buckets and inserted elements which, when exceeded, will cause rehashing of the table with twice the number of buckets.

This generally works very well, but only if the hash function is good, i.e. does not result in more than the statistically expected number of collisions for your particular input set. String.hashCode() is good in this regard, but this was not always so. Allegedly, prior to Java 1.2 it only inlcuded every n'th character. This was faster, but caused predictable collisions for all String sharing each n'th character - very bad if you're unluck enough to have such regular input, or if someone want to do a DOS attack on your app.

---

I direct you to the answer here. While it is not a bad idea to use strings( @CPerkins explained why, perfectly), storing the values in a hashmap with integer keys is better, since it is generally quicker (although unnoticeably) and has lower chance (actually, no chance) of collisions.

See this chart of collisions using 216553 keys in each case, (stolen from this post, reformatted for our discussion)

Hash           Lowercase      Random UUID  Numbers 
=============  =============  ===========  ==============
Murmur            145 ns      259 ns          92 ns
                    6 collis    5 collis       0 collis
FNV-1a            152 ns      504 ns          86 ns
                    4 collis    4 collis       0 collis
FNV-1             184 ns      730 ns          92 ns
                    1 collis    5 collis       0 collis*
DBJ2a             158 ns      443 ns          91 ns
                    5 collis    6 collis       0 collis***
DJB2              156 ns      437 ns          93 ns
                    7 collis    6 collis       0 collis***
SDBM              148 ns      484 ns          90 ns
                    4 collis    6 collis       0 collis**
CRC32             250 ns      946 ns         130 ns
                    2 collis    0 collis       0 collis

Avg Time per key    0.8ps       2.5ps         0.44ps
Collisions (%)      0.002%      0.002%         0%

Of course, the number of integers is limited to 2^32, where as there is no limit to the number of strings (and there is no theoretical limit to the amount of keys that can be stored in a HashMap). If you use a long (or even a float), collisions will be inevitable, and therefore no "better" than a string. However, even despite hash collisions, put() and get() will always put/get the correct key-value pair (See edit below).

In the end, it really doesn't matter, so use whatever is more convenient. But if convenience makes no difference, and you do not intend to have more than 2^32 entries, I suggest you use ints as keys.

---

EDIT

While the above is definitely true, NEVER use "StringKey".hashCode() to generate a key in place of the original String key for performance reasons- 2 different strings can have the same hashCode, causing overwriting on your put() method. Java's implementation of HashMap is smart enough to handle strings (any type of key, actually) with the same hashcode automatically, so it is wise to let Java handle these things for you.

---

You are talking about hash collisions. Hash collisions are an issue regardless of the type being hashCode'd. All classes that use hashCode (e.g. HashMap) handle hash collisions just fine. For example, HashMap can store multiple objects per bucket.

Don't worry about it unless you are calling hashCode yourself. Hash collisions, though rare, don't break anything.

참고URL : https://stackoverflow.com/questions/1516549/bad-idea-to-use-string-key-in-hashmap