해시 테이블

2002 년 6 월 21 일

Q : Hashtable에서 객체를 키로 사용할 때 Object 클래스에서 무엇을 재정의해야하며 그 이유는 무엇입니까?

A : 당신이에서 사용하기 위해 자신의 키 객체를 생성 할 때 Hashtable, 당신은 오버라이드 (override) 할 필요가 Object.equals()Object.hashCode()이후 방법을 Hashtable사용하는 키의 조합 hashCode()equals()방법 가게를하고 신속하게 항목을 검색 할 수 있습니다. 을 재정의 할 때 equals()항상을 재정의 하는 것도 일반적인 규칙입니다 hashCode().

이유에 대해 더 알아보기

좀 더 심층적 인 설명은 Hashtable의 저장 및 검색 메커니즘을 이해하는 데 도움이됩니다 . A Hashtable는 키 / 값 쌍을 저장하는 버킷을 내부적으로 포함합니다. Hashtable키의 해시 코드를 결정하는 데 사용하는 키 / 값 쌍 매핑해야 버킷있다.

그림 1은 a Hashtable와 해당 버킷을 보여줍니다 . 에 키 / 값을 전달 Hashtable하면 키의 해시 코드를 쿼리합니다. Hashtable코드의 버킷을 결정하는 것을 사용하는 키 / 값을 배치한다. 해시 코드가 0 인 경우에 따라서, 예를 들면,이 Hashtable해시 코드는 두 가지의 경우, 마찬가지로 통 0에 값을 배치 Hashtable장소 버킷 2 (이것은 단순한 일례이다 내로 값, 상기는 Hashtable상기 제 1 해시 코드를 마사지 할 Hashtable버킷 외부에 값을 삽입하려고하지 않습니다.)

이러한 방식으로 해시 코드를 사용하면는 Hashtable값을 검색하려고 할 때 값을 배치 한 버킷을 신속하게 결정할 수도 있습니다.

그러나 해시 코드는 그림의 절반에 불과합니다. 해시 코드 Hashtable는 키 / 값을 삭제할 버킷 만 알려줍니다 . 그러나 때로는 여러 객체가 충돌 이라고하는 이벤트 인 동일한 버킷에 매핑 될 수 있습니다 . Java에서는 Hashtable동일한 버킷에 여러 값을 배치하여 충돌에 응답합니다 (다른 구현에서는 충돌을 다르게 처리 할 수 ​​있음). 그림 2는 Hashtable몇 번의 충돌 후 a가 어떻게 생겼는지 보여줍니다 .

이제 get()Bucket 0에 매핑되는 키를 사용하여 호출한다고 가정합니다. Hashtable이제는 요청 된 값을 찾기 위해 Bucket 0의 키 / 값 쌍을 통해 순차적 검색을 수행해야합니다. 이 조회를 수행하기 위해 Hashtable는 다음 단계를 실행합니다.

  1. 키의 해시 코드 쿼리
  2. 해시 코드가 제공하는 버킷에있는 키 / 값 목록을 검색합니다.
  3. 전달 된 키와 동일한 키를 get()찾을 때까지 각 항목을 순차적으로 검색합니다.

내가 아는 짧은 질문에 대한 긴 대답이지만 더 나빠집니다. 적절하게 재정의 equals()하고 hashCode()사소하지 않은 연습입니다. 두 방법의 계약을 보장하려면 각별한주의를 기울여야합니다.

equals () 구현시

equals()Javadoc 에 따르면 메소드는 다음 규칙을 따라야합니다.

"이 equals()메서드는 등가 관계를 구현합니다.
  • 반사적입니다. 참조 값 x에 대해 x.equals(x)true를 반환해야합니다.
  • 대칭입니다. 참조 값 x 및 y에 대해 x.equals(y)true를 반환하는 경우에만 y.equals(x)true를 반환해야합니다.
  • 전 이적 : 참조 값 x, y 및 z에 대해 x.equals(y)true를 y.equals(z)반환 하고 true를 반환 하면 true를 반환 x.equals(z)해야합니다.
  • 일관성 : 참조 값 x 및 y x.equals(y)에 대해 객체의 같음 비교에 사용 된 정보가 수정되지 않은 경우 여러 번 호출하면 일관성있게 true를 반환하거나 지속적으로 false를 반환합니다.
  • null이 아닌 참조 값 x의 경우 x.equals(null)false를 반환해야합니다. "

효과적인 자바 조슈아 블로흐는 효과적인 작성을위한 5 단계 레시피 제공 equals()방법. 다음은 코드 형식의 레시피입니다.

public class EffectiveEquals {private int valueA; private int valueB; . . . public boolean equals (Object o) {if (this == o) {// 1 단계 : == 테스트 수행 return true; } if (! (o instanceof EffectiveEquals)) {// 2 단계 : 검사 인스턴스 return false; } EffectiveEquals ee = (EffectiveEquals) o; // 3 단계 : 캐스트 인수 // 4 단계 : 각 중요한 필드에 대해 동일한 지 확인합니다. // 기본 요소의 경우 == // 객체의 경우 equals ()를 사용하지만 // null 케이스도 처리해야합니다. 첫 번째 반환 ee.valueA == valueA && ee.valueB == valueB; }. . . }

참고 :null instanceof EffectiveEquals 는 false로 평가 되므로 null 검사를 수행 할 필요가 없습니다 .

마지막으로 5 단계에서 equals()의 계약 으로 돌아가서 equals()방법이 반사적이고 대칭 적이며 전이 적인지 자문 해보십시오 . 그렇지 않은 경우 수정하십시오!

hashCode () 구현시

대한 hashCode()의 일반 계약, Javadoc을 말한다 :

  • "Java 애플리케이션을 실행하는 동안 동일한 객체에서 두 번 이상 호출 될 때마다 객체에 대한 hashCode()같음 비교에 사용 된 정보가 수정되지 않으면 메서드는 일관되게 동일한 정수를 반환해야합니다.이 정수는 하나에서 일관성을 유지할 필요가 없습니다. 동일한 응용 프로그램의 다른 실행에 응용 프로그램 실행.
  • equals(Object)메서드 에 따라 두 개체가 동일한 경우 두 개체 각각에서 메서드를 호출 hashCode()하면 동일한 정수 결과가 생성되어야합니다.
  • It is not required that if two objects are unequal according to the equals(java.lang.Object method, then calling the hashCode() method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hashtables."

Creating a properly working hashCode() method proves difficult; it becomes even more difficult if the object in question is not immutable. You can calculate a hashcode for a given object in many ways. The most effective method bases the number upon the object's fields. Moreover, you can combine these values in various ways. Here are two popular approaches:

  • You can turn the object's fields into a string, concatenate the strings, and return the resulting hashcode
  • 각 필드의 해시 코드를 추가하고 결과를 반환 할 수 있습니다.

다른보다 철저한 접근 방식이 존재하지만 앞서 언급 한 두 가지 접근 방식이 이해하고 구현하기가 가장 쉽습니다.

Tony Sintes는 독립적 인 컨설턴트이자 서로 다른 엔터프라이즈 시스템 및 교육을 연결하는 전문 컨설팅 회사 인 First Class Consulting의 설립자입니다. First Class Consulting 외부에서 Tony는 활발한 프리랜서 작가이자 Sams Teach Yourself Object-Oriented Programming in 21 Days (Sams, 2001; ISBN : 0672321092)의 저자입니다.

이 주제에 대해 더 알아보기

  • Hashtable Javadoc의 경우 다음으로 이동하십시오.

    //java.sun.com/j2se/1.4/docs/api/java/util/Hashtable.html

  • Vipan Singla의 "equals () 및 hashCode () 구현"은 equals () 및 hashCode () 메서드 재정의에 대한 심층 토론을 제공합니다.

    //www.vipan.com/htdocs/hashcode_help.html

  • The Object.equals() Javadoc

    //java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#equals(java.lang.Object)

  • The Object.hashCode() Javadoc

    //java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#hashCode()

  • For Joshua Bloch's Effective Java Programming Language Guide (Addison Wesley Professional, 2001; ISBN0201310058), go to

    //www.amazon.com/exec/obidos/ASIN/0201310058/javaworld

  • For more articles on Java classes and methods, browse the APIs section of JavaWorld's Topical Index

    //www.javaworld.com/channel_content/jw-apis-index.shtml

  • Want more? See the Java Q&A index page for the full Q&A catalog

    //www.javaworld.com/columns/jw-qna-index.shtml

  • 업계 최고의 전문가들이 제공하는 100 개 이상의 통찰력있는 Java 팁을 보려면 JavaWorldJava Tips 색인 페이지를 방문 하십시오.

    //www.javaworld.com/columns/jw-tips-index.shtml

  • Java Beginner 토론 에서 Java 기본 사항 알아보기

    //forums.idg.net/[email protected]@.ee6b804

  • 가입 JavaWorld 의 무료 주간 코어 자바 이메일 뉴스 레터

    //www.javaworld.com/subscribe

  • .net의 자매 간행물에서 다양한 IT 관련 기사를 찾을 수 있습니다.

이 이야기 "Hashtables"는 원래 JavaWorld에 의해 출판되었습니다.