해시테이블은 애플리케이션 성능을 최적화하는 유용한 방법을 제공합니다.
해시테이블은 컴퓨터 분야에서 새로운 개념이 아닙니다. 이는 오늘날의 표준으로는 매우 느린 컴퓨터 처리 속도를 높이기 위해 설계되었으며, 많은 데이터 항목을 쿼리할 때 특정 항목을 빠르게 찾을 수 있도록 해줍니다. 최신 머신은 수천 배 더 빠르지만 해시테이블은 여전히 애플리케이션에서 최고의 성능을 얻는 데 유용한 도구입니다.
소규모 기업의 고객 기록과 같은 약 1000개의 기록이 포함된 데이터 파일과 처리를 위해 기록을 메모리로 읽어들이는 프로그램이 있다고 상상해 보십시오. 각 기록에는 고유한 5자리 고객 ID 번호, 고객 이름, 주소, 계좌 잔액 등이 포함됩니다. 레코드가 고객 ID 번호별로 정렬되지 않는다고 가정합니다. 따라서 프로그램이 특정 고객 레코드를 찾기 위해 고객 번호를 "키"로 사용하려는 경우 이를 찾는 유일한 방법은 각 레코드를 연속적으로 검색하는 것입니다. 때로는 필요한 레코드를 빨리 찾을 수도 있지만 때로는 프로그램이 필요한 레코드를 찾기 전에 마지막 레코드를 거의 검색한 경우도 있습니다. 1,000개의 레코드 중에서 검색하려면 하나의 레코드를 찾으려면 프로그램에서 평균 500.5((1000 + 1)/2)개의 레코드를 확인해야 합니다. 데이터를 자주 조회해야 하는 경우 레코드를 찾는 더 빠른 방법이 필요할 수 있습니다.
검색 속도를 높이는 한 가지 방법은 기록을 여러 조각으로 나누어 하나의 큰 목록을 검색하는 대신 여러 개의 짧은 목록을 검색하는 것입니다. 숫자로 된 고객 ID 번호의 경우 10개의 목록을 생성할 수 있습니다. 하나는 0으로 시작하는 ID 번호 목록, 하나는 1로 시작하는 ID 번호 목록 등입니다. 따라서 고객 ID 번호 38016을 찾으려면 3으로 시작하는 목록만 검색하면 됩니다. 1,000개의 레코드가 있고 각 목록의 평균 길이가 100개(1,000개의 레코드를 10개의 목록으로 나눈 값)이면 레코드를 검색하기 위한 평균 비교 횟수는 약 50개 정도로 떨어집니다(그림 1 참조).
물론 고객 수 10명 중 약 1명이 0으로 시작하고 또 다른 10%가 1로 시작하는 등의 경우에는 이 접근 방식이 효과적일 것입니다. 고객 수의 90%가 0으로 시작한다면 해당 목록에는 900개의 레코드가 있으며 조회당 평균 450번의 비교가 필요합니다. 또한 프로그램이 수행해야 하는 검색의 90%는 0으로 시작하는 숫자에 대한 것입니다. 따라서 평균 비교 수치는 단순한 수학 연산의 범위를 훨씬 뛰어넘습니다.
키 값의 숫자 분포에 관계없이 각 목록이 거의 동일한 항목을 갖도록 목록의 레코드를 배포할 수 있다면 더 좋을 것입니다. 우리는 고객 수를 함께 혼합하고 결과를 더 잘 배포할 수 있는 방법이 필요합니다. 예를 들어, 숫자의 각 자릿수에 큰 숫자(숫자의 위치에 따라 다름)를 곱하고 결과를 더하여 총합을 계산한 다음 이 숫자를 10으로 나누고 나머지를 인덱스로 제공할 수 있습니다. 값(인덱스). 기록을 읽으면 프로그램은 고객 번호에 대해 이 해시 함수를 실행하여 기록이 속한 목록을 결정합니다. 사용자가 쿼리해야 하는 경우 동일한 해시 함수를 고객 번호에 대한 "키"로 사용하여 올바른 목록을 검색할 수 있습니다. 이와 같은 데이터 구조를 해시테이블이라고 합니다.
Java 의 해시테이블
Java에는 다목적 해시테이블 메커니즘을 제공하는 java.util.Hashtable 및 java.util.HashMap 이라는 두 가지 클래스가 포함되어 있습니다. 두 클래스는 매우 유사하며 일반적으로 동일한 공용 인터페이스를 제공합니다. 그러나 두 가지에는 몇 가지 중요한 차이점이 있는데 이에 대해서는 나중에 설명하겠습니다.
Hashtable 및 HashMap 객체를 사용하면 키와 값을 결합하고 put () 메서드를 사용하여 키/값 쌍을 테이블에 입력할 수 있습니다. 그런 다음 get() 메서드를 호출하고 키를 매개변수로 전달하여 값을 가져올 수 있습니다. 키와 값은 두 가지 기본 요구 사항을 충족하는 한 모든 개체가 될 수 있습니다. 키와 값은 객체여야 하기 때문에 Integer(int)와 같은 메소드를 사용하여 기본 유형을 객체로 변환해야 한다는 점에 유의하세요.
특정 클래스의 객체를 키로 사용하기 위해서는 해당 클래스에서 equals()와 hashCode()라는 두 가지 메서드를 제공해야 합니다. 이 두 메소드는 java.lang.Object 에 있으므로 모든 클래스는 이 두 메소드를 상속할 수 있습니다. 그러나 Object 클래스에서 이 두 메소드를 구현하는 것은 일반적으로 쓸모가 없으므로 일반적으로 이 두 메소드를 직접 오버로드해야 합니다.
Equals() 메서드는 해당 개체를 다른 개체와 비교하고 두 개체가 동일한 정보를 나타내는 경우 true를 반환합니다. 이 방법은 또한 두 개체가 모두 동일한 클래스에 속하는지 확인합니다. Object.equals()는 두 참조 객체가 동일한 객체인 경우 true를 반환합니다. 이는 일반적으로 이 메서드가 적합하지 않은 이유를 설명합니다. 대부분의 경우 필드별로 비교할 수 있는 방법이 필요하므로 동일한 데이터를 나타내는 서로 다른 개체를 동일한 것으로 간주합니다.
HashCode() 메서드는 객체의 내용을 사용하여 해시 함수를 수행하여 int 값을 생성합니다. Hashtable과 HashMap은 이 값을 사용하여 키/값 쌍이 어느 버킷(또는 목록)에 있는지 파악합니다.
예를 들어 String 클래스를 살펴보면 이 두 가지 메서드를 구현하는 자체 메서드가 있기 때문입니다. String.equals()는 두 개의 String 객체를 문자별로 비교하고 문자열이 동일하면 true를 반환합니다.
다음과 같이 코드 코드를 복사합니다 .
String myName = "아인슈타인";
// 다음 테스트는
// 항상 참
if ( myName.equals("아인슈타인") )
{ ...
String.hashCode()는 문자열에 대해 해시 함수를 실행합니다. 문자열에 있는 각 문자의 숫자 코드에 31을 곱하고 결과는 문자열에서 문자의 위치에 따라 달라집니다. 그런 다음 이러한 계산 결과를 추가하여 총계를 계산합니다. 이 프로세스는 복잡해 보일 수 있지만 가치의 더 나은 분배를 보장합니다. 또한 결과가 고유하다는 확신을 갖고 자신만의 hashCode() 메서드를 개발할 때 얼마나 멀리 갈 수 있는지 보여줍니다.
예를 들어, 해시테이블을 사용하여 책 카탈로그를 구현하고 책의 ISBN 번호를 검색 키로 사용한다고 가정해 보겠습니다. String 클래스를 사용하여 세부사항을 전달하고 equals() 및 hashCode() 메소드를 준비할 수 있습니다(목록 1 참조). put () 메소드를 사용하여 해시테이블에 키/값 쌍을 추가할 수 있습니다(목록 2 참조).
Put () 메서드는 두 개의 매개 변수를 허용하며 둘 다 Object 유형입니다. 첫 번째 매개변수는 키이고, 두 번째 매개변수는 값입니다. Put () 메서드는 키의 hashCode() 메서드를 호출하고 결과를 테이블의 목록 수로 나눕니다. 나머지를 인덱스 값으로 사용하여 레코드가 추가되는 목록을 결정합니다. 키는 테이블에서 고유합니다. 기존 키를 사용하여 put ()을 호출하면 일치하는 항목이 새 값을 참조하고 이전 값이 반환되도록 수정됩니다( 키가 테이블에 존재하지 않는 경우). , put ()은 null 값을 반환합니다).
테이블에서 값을 읽으려면 get() 메소드와 함께 검색 키를 사용합니다. 올바른 유형으로 변환된 객체 참조를 반환합니다.
다음과 같이 코드 코드를 복사합니다 .
BookRecord br =
(BookRecord)isbnTable.get(
"0-345-40946-9");
System.out.println(
"저자: " + br.저자
+ " 제목: " + br.제목);
또 다른 유용한 방법은 get()과 거의 동일하게 사용되는 제거()입니다. 이 방법은 테이블에서 항목을 제거하고 이를 호출 프로그램에 반환합니다.
나만의 수업
기본 유형을 키로 사용하려면 동일한 유형의 객체를 생성해야 합니다. 예를 들어 정수 키를 사용하려면 Integer(int) 생성자를 사용하여 정수에서 객체를 생성해야 합니다. Integer, Float, Boolean 등의 모든 래퍼 클래스는 프리미티브 값을 객체로 취급하며, equals() 및 hashCode() 메서드를 오버로드하므로 키로 사용할 수 있습니다. JDK에서 제공되는 다른 많은 클래스도 이와 유사합니다(Hashtable 및 HashMap 클래스도 자체적인 equals() 및 hashCode() 메서드를 구현함). 그러나 클래스의 객체를 해시테이블 키로 사용하기 전에 설명서를 확인해야 합니다. 또한 equals() 및 hashCode()가 어떻게 구현되는지 확인하려면 클래스 소스를 확인해야 합니다. 예를 들어 Byte, Character, Short, Integer는 모두 표현된 정수 값을 해시 코드로 반환합니다. 이는 귀하의 요구에 적합할 수도 있고 그렇지 않을 수도 있습니다.
Java 에서 해시테이블 사용
키로 정의한 클래스의 객체를 사용하는 해시테이블을 생성하려면 해당 클래스의 equals() 및 hashCode() 메서드가 유용한 값을 제공하는지 확인해야 합니다. 먼저 확장한 클래스를 살펴보고 구현이 요구 사항을 충족하는지 확인하세요. 그렇지 않은 경우 메서드를 오버로드해야 합니다.
모든 equals() 메소드의 기본 설계 제약은 전달된 객체가 동일한 클래스에 속하고 해당 데이터 필드가 동일한 데이터를 나타내는 값으로 설정된 경우 true를 반환해야 한다는 것입니다. 또한 메소드에 빈 인수를 전달하는 경우 코드가 다음을 반환하는지 확인해야 합니다.
다음과 같이 코드 코드를 복사합니다 .
false: 공개 부울 같음(객체 o)
{
if ((o == null)
|| !(o 인스턴스of myClass))
{
거짓을 반환;
}
// 이제 데이터 필드를 비교합니다...
또한 hashCode() 메서드를 디자인할 때 염두에 두어야 할 몇 가지 규칙이 있습니다. 첫째, 메소드는 메소드가 호출된 횟수에 관계없이(물론 호출 간에 객체의 내용이 변경되지 않는 한) 특정 객체에 대해 동일한 값을 반환해야 합니다. 객체를 해시테이블 키로 사용하는 경우 이는 다음과 같습니다. 피하세요). 둘째, equals() 메소드로 정의된 두 객체가 동일한 경우 동일한 해시 코드도 생성해야 합니다. 셋째, 이는 원칙이라기보다 지침에 가깝습니다. 개체 내용에 따라 다른 결과가 생성되도록 방법을 설계해야 합니다. 때때로 다른 개체가 동일한 해시 코드를 생성하는 경우는 중요하지 않습니다. 그러나 메소드가 1~10 범위의 값만 반환할 수 있는 경우에는 해시 테이블에 목록이 몇 개 있는지 관계없이 10개의 목록만 사용할 수 있습니다.
equals() 및 hashCode()를 디자인할 때 염두에 두어야 할 또 다른 요소는 성능입니다. put () 또는 get()을 호출할 때마다 hashCode()를 호출하여 올바른 목록을 찾습니다. get()이 키를 찾기 위해 목록을 검색할 때 목록의 각 요소에 대해 equals()를 호출합니다. 특히 다른 사용자가 실행 속도가 중요한 고성능 애플리케이션에서 클래스를 사용하기를 원할 수 있으므로 클래스를 공개적으로 사용할 수 있도록 계획하는 경우 가능한 한 빠르고 효율적으로 실행되도록 이러한 메서드를 구현하십시오.
해시테이블 성능
해시테이블의 효율성에 영향을 미치는 주요 요인은 테이블에 포함된 목록의 평균 길이입니다. 평균 검색 시간은 이 평균 길이와 직접적인 관련이 있기 때문입니다. 분명히 평균 길이를 줄이려면 해시 테이블의 목록 수를 늘려야 합니다. 목록 수가 너무 많아서 대부분 또는 모든 목록에 하나의 레코드만 포함되어 있으면 최상의 검색 효율성을 얻을 수 있습니다. 그러나 이는 너무 지나친 것일 수 있습니다. 해시테이블에 데이터 항목보다 훨씬 많은 목록이 있는 경우 이러한 메모리 비용을 들일 필요가 없으며 어떤 경우에는 사람들이 이 접근 방식을 받아들이는 것이 불가능합니다.
이전 예에서 우리는 보유하고 있는 레코드 수(1,000)를 미리 알고 있었습니다. 이를 알면 검색 속도와 메모리 사용 효율성 사이에서 최상의 절충안을 달성하기 위해 해시 테이블에 포함해야 하는 목록 수를 결정할 수 있습니다. 그러나 많은 경우 처리할 레코드 수를 미리 알 수 없으며, 데이터를 읽는 파일이 지속적으로 증가하거나 레코드 수가 날마다 크게 변경될 수 있습니다.
Hashtable 및 HashMap 클래스는 항목이 추가될 때 테이블을 동적으로 확장하여 이 문제를 처리합니다. 두 클래스 모두 테이블의 초기 목록 수와 로드 요소를 매개변수로 받아들이는 생성자를 갖고 있습니다.
공개 해시테이블(
int 초기 용량,
부동 하중 인자)
공개 해시맵(
int 초기용량,
부동 하중 인자)
이 두 숫자를 곱하여 임계값을 계산합니다. 해시 테이블에 새 항목이 추가될 때마다 개수가 업데이트되고, 개수가 임계값을 초과하면 테이블이 재설정(재해시)됩니다. (목록 크기는 이전 크기의 2배에 1을 더한 값으로 증가하고 모든 항목은 올바른 목록으로 이동됩니다.) 기본 생성자는 초기 용량을 11로, 로드 요소를 0.75로 설정하므로 임계값은 8입니다. 9번째 레코드가 테이블에 추가되면 해시 테이블의 크기가 조정되어 23개의 목록이 생기고 새로운 임계값은 17(23*0.75의 정수 부분)이 됩니다. 로드 비율은 해시 테이블의 평균 목록 수에 대한 상한입니다. 이는 기본적으로 해시 테이블에 둘 이상의 레코드가 포함된 목록이 거의 없다는 것을 의미합니다. 10개의 목록에 1,000개의 레코드가 분산되어 있는 원래 예를 비교해 보세요. 기본값을 사용하면 이 테이블은 1,500개 이상의 목록을 포함하도록 확장됩니다. 하지만 당신은 이것을 통제할 수 있습니다. 로드 요소를 곱한 목록 수가 처리 중인 항목 수보다 크면 테이블이 다시 만들어지지 않으므로 아래 예를 따를 수 있습니다.
다음과 같이 코드 코드를 복사합니다 .
// 테이블은 테이블이 나올 때까지 다시 해시되지 않습니다.
// 1,100개의 항목이 있습니다(10*110):
해시테이블 myHashTable =
새로운 해시테이블(10, 110.0F);
빈 목록을 위한 메모리를 절약하고 싶지 않고 추가 검색 시간(임베디드 시스템에서 발생할 수 있음)을 고려하지 않는 한 이 작업을 수행하고 싶지 않을 것입니다. 그러나 재설정은 계산 비용이 많이 들고 재설정이 발생하지 않도록 보장하므로 이 접근 방식이 유용할 수 있습니다.
put ()을 호출하면 테이블이 커질 수 있지만(목록 수 증가), Remove()를 호출해도 반대 효과는 발생하지 않습니다. 따라서 큰 테이블이 있고 거기에서 대부분의 항목을 삭제하면 크지만 대부분 비어 있는 테이블이 됩니다.
해시테이블과 해시맵
Hashtable 클래스와 HashMap 클래스 사이에는 세 가지 중요한 차이점이 있습니다. 첫 번째 차이점은 주로 역사적인 이유 때문입니다. Hashtable은 이전 Dictionary 클래스를 기반으로 하며 HashMap은 Java 1.2에 도입된 Map 인터페이스의 구현입니다.
아마도 가장 중요한 차이점은 Hashtable의 메서드는 동기식이지만 HashMap의 메서드는 그렇지 않다는 것입니다. 즉, 특별한 조치를 취하지 않고도 다중 스레드 애플리케이션에서 Hashtable을 사용할 수 있지만 마찬가지로 HashMap에 대한 외부 동기화를 제공해야 합니다. 편리한 방법은 스레드로부터 안전한 Map 객체를 생성하고 이를 캡슐화된 객체로 반환하는 Collections 클래스의 정적 syncinizedMap() 메서드를 사용하는 것입니다. 이 객체의 메서드를 사용하면 기본 HashMap에 동기적으로 액세스할 수 있습니다. 결과적으로 필요하지 않을 때(예: 단일 스레드 애플리케이션에서) Hashtable에서 동기화를 중단할 수 없으며 동기화로 인해 많은 처리 오버헤드가 추가됩니다.
세 번째 차이점은 HashMap만이 테이블 항목의 키나 값으로 null 값을 사용할 수 있다는 것입니다. HashMap에서 단 하나의 레코드만 빈 키가 될 수 있지만 항목 수에는 제한이 없으며 빈 값이 될 수 있습니다. 즉, 테이블에서 검색 키를 찾을 수 없거나 검색 키를 찾았지만 null 값인 경우 get()은 null을 반환합니다. 필요한 경우 containKey() 메서드를 사용하여 두 상황을 구분합니다.
일부 정보에 따르면 동기화가 필요한 경우 Hashtable을 사용하고 그렇지 않으면 HashMap을 사용하는 것이 좋습니다. 그러나 HashMap은 필요할 때 동기화할 수 있기 때문에 HashMap은 Hashtable보다 더 많은 기능을 가지고 있고, 오래된 클래스를 기반으로 하지 않기 때문에 다양한 상황에서 HashMap이 Hashtable보다 선호된다고 생각하는 사람들도 있습니다.
속성 정보
때로는 해시테이블을 사용하여 키 문자열을 값 문자열에 매핑할 수도 있습니다. DOS, Windows 및 Unix에는 환경 문자열의 몇 가지 예가 있습니다. 예를 들어 키 문자열 PATH는 값 문자열 C:/WINDOWS;C:/WINDOWS/SYSTEM에 매핑됩니다. 해시테이블은 이를 표현하는 간단한 방법이지만 Java는 다른 방법을 제공합니다.
Java .util.Properties 클래스는 문자열 키 및 값과 함께 사용하도록 설계된 Hashtable의 하위 클래스입니다. Properties 객체의 사용법은 Hashtable의 사용법과 유사하지만 클래스는 여러분이 알아야 할 두 가지 시간 절약 방법을 추가합니다.
Store() 메서드는 Properties 개체의 내용을 읽을 수 있는 형식으로 파일에 저장합니다. Load() 메서드는 정반대이며, 파일을 읽고 키와 값을 포함하도록 Properties 개체를 설정하는 데 사용됩니다.
Properties는 Hashtable을 확장하므로 슈퍼클래스의 put () 메서드를 사용하여 String 객체가 아닌 키와 값을 추가할 수 있습니다. 이는 바람직하지 않습니다. 또한 String 개체가 포함되지 않은 Properties 개체와 함께 store()를 사용하면 store()가 실패합니다. put () 및 get() 대신 String 매개변수를 사용하는 setProperty() 및 getProperty()를 사용해야 합니다.
좋습니다. 이제 처리 속도를 높이기 위해 해시테이블을 사용하는 방법을 알게 되기를 바랍니다.