해시 테이블의 기초?

해시 테이블의 기초?

---

해시 테이블의 기본 개념에 대해 꽤 혼란 스럽습니다. 해시를 코딩한다면 어떻게 시작할까요? 해시 테이블과 일반 배열의 차이점은 무엇입니까?

기본적으로 누군가가이 질문에 답하면 내 모든 질문에 답할 수 있다고 생각합니다. 무작위로 생성 된 100 개의 숫자 (키로)가 있다면 어떻게 해시 테이블을 구현할 수 있으며 왜 배열보다 유리할까요?

의사 코드 또는 Java는 학습 도구로 높이 평가 될 것입니다.

---

지금까지의 답변은 해시 테이블을 정의하고 일부 이론을 설명하는 데 도움이되었지만 예제를 통해 더 나은 느낌을 얻을 수 있다고 생각합니다.

해시 테이블과 일반 배열의 차이점은 무엇입니까?

해시 테이블과 배열은 모두 데이터를 저장하고 검색 할 수있는 구조입니다. 둘 다 색인 을 지정하고 이와 연관된 값을 검색 할 수 있습니다. Daniel Spiewak이 언급했듯이 차이점은 배열의 인덱스는 순차적 인 반면 해시 테이블 의 인덱스는 연관된 데이터 의 값을 기반으로한다는 것입니다.

해시 테이블을 사용하는 이유는 무엇입니까?

해시 테이블은 많은 양의 데이터, 특히 쉽게 검색 할 수없는 데이터에서 항목을 검색하는 매우 효율적인 방법을 제공 할 수 있습니다. ( "대형은"여기에 의미 ginormous 한 이 순차적 인 검색을 수행하는 데 시간이 오래 걸릴 것이라는 의미에서).

해시를 코딩한다면 어떻게 시작할까요?

문제 없어요. 가장 간단한 방법은 숫자 N(일반적으로 정수) 를 반환하는 데이터에 대해 수행 할 수있는 임의의 수학 연산을 만드는 것 입니다. 그런 다음이 숫자를 '버킷'배열의 색인으로 사용하고 데이터를 버킷 #에 저장합니다 N. 요령은 나중에 쉽게 찾을 수 있도록 다른 버킷에 값을 배치하는 작업을 선택하는 것입니다.

예 : 대형 쇼핑몰은 구매자가 주차 한 위치를 기억할 수 있도록 고객의 자동차와 주차 위치에 대한 데이터베이스를 유지합니다. 데이터베이스 저장 make, color, license plate,와 parking location. 상점을 떠날 때 구매자는 제조업체와 색상을 입력하여 자신의 차를 찾습니다. 데이터베이스는 번호판 및 주차 공간의 (상대적으로 짧은) 목록을 반환합니다. 빠른 스캔으로 구매자의 차를 찾습니다.

SQL 쿼리로이를 구현할 수 있습니다.

SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"

데이터가 기본적으로 목록에 불과한 배열에 저장된 경우 모든 일치 항목에 대해 배열을 스캔하여 쿼리를 구현하는 것을 상상할 수 있습니다.

반면에 해시 규칙을 상상해보십시오.

제조업체 및 색상에있는 모든 문자의 ASCII 문자 코드를 추가하고 100으로 나누고 나머지를 해시 값으로 사용합니다.

이 규칙은 각 항목을 0에서 99 사이의 숫자로 변환하여 기본적으로 데이터를 100 개의 버킷 으로 정렬 합니다. 고객이 자동차를 찾아야 할 때마다 제조업체와 색상을 해시 하여 정보가 포함 된 100 개 중 하나의 버킷 을 찾을 수 있습니다. 즉시 검색을 100 배 줄였습니다!

이제 수십 개의 기준에 따라 검색되는 수백만 개의 항목이있는 데이터베이스와 같이 방대한 양의 데이터로 예제를 확장하십시오. "좋은"해시 함수는 추가 검색을 최소화하는 방식으로 데이터를 버킷에 배포하여 상당한 시간을 절약합니다.

---

먼저 해시 함수가 무엇인지 이해해야합니다. 해시 함수는 키 (예 : 임의 길이의 문자열)를 가져와 가능한 한 고유 한 숫자 를 반환하는 함수 입니다. 동일한 키는 항상 동일한 해시를 반환해야합니다. Java의 정말 간단한 문자열 해싱 함수는 다음과 같습니다.

public int stringHash(String s) {
    int h = s.length();
    for(char c : s.toCharArray()) {
        h ^= c;
    }
    return h;
}

http://www.azillionmonkeys.com/qed/hash.html 에서 좋은 해시 함수를 공부할 수 있습니다 .

이제 해시 맵은이 해시 값을 사용하여 값을 배열에 배치합니다. 단순한 자바 방법 :

public void put(String key, Object val) {
    int hash = stringHash(s) % array.length;
    if(array[hash] == null) {
        array[hash] = new LinkedList<Entry<String, Object> >();
    }
    for(Entry e : array[hash]) {
        if(e.key.equals(key)){
            e.value = val;
            return;
        }
    }
    array[hash].add(new Entry<String, Object>(key, val));
}

(이 맵은 고유 키를 적용합니다. 모든 맵이 적용되는 것은 아닙니다.)

두 개의 다른 키가 동일한 값으로 해시되거나 두 개의 다른 해시가 동일한 배열 인덱스에 매핑 될 수 있습니다. 이를 처리하기위한 많은 기술이 있습니다. 가장 간단한 방법은 각 배열 인덱스에 대해 연결 목록 (또는 이진 트리)을 사용하는 것입니다. 해시 함수가 충분하면 선형 검색이 필요하지 않습니다.

이제 키를 찾습니다.

public Object get(String key) {
    int hash = stringHash(key) % array.length;
    if(array[hash] != null) {
        for(Entry e : array[hash]) {
            if(e.key.equals(key))
                return e.value;
        }
    }

    return null;
}

---

해시 테이블은 연관성 이 있습니다 . 이것은 선형 데이터 구조 인 배열과 큰 차이가 있습니다. 배열을 사용하면 다음과 같이 할 수 있습니다.

int[] arr = ...
for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i] + 1);
}

정확한 메모리 오프셋 ( i) 을 지정하여 배열에서 요소를 얻는 방법을 확인하십시오 . 이는 키 / 값 쌍을 저장하고 나중에 키를 기반으로 값을 검색 할 수있는 해시 테이블과 대조됩니다.

Hashtable<String, Integer> table = new Hashtable<String, Integer>();
table.put("Daniel", 20);
table.put("Chris", 18);
table.put("Joseph", 16);

위의 표를 사용하여 다음과 같은 호출을 할 수 있습니다.

int n = table.get("Chris");

... 그리고 그 n가치는 18.

나는 이것이 아마도 대부분의 질문에 답할 것이라고 생각합니다. 해시 테이블의 구현은 상당히 흥미로운 주제이며, 위키피디아가 잘 다루고 있습니다 .

---

"해시 테이블이 키를 조회하는 방식과 키가 생성되는 방식에 더 관심이 있습니다."

1. 해싱은 키 개체를 숫자로 변환합니다. 이를 "해싱"이라고합니다. 객체에서 해시를 만듭니다. 해시 함수를 참조하십시오 . 예를 들어, 문자열의 바이트를 합산하는 것은 표준 해시 기술입니다. 해시를 관리 가능한 크기로 유지하기 위해 모듈로 2 ³² 합계를 계산합니다 . 해시는 항상 같은 대답을 제공합니다. 이것은 O (1)입니다.

2. 숫자는 HashTable에서 "슬롯"을 제공합니다. 임의의 키 객체가 주어지면 해시 값은 해시 값을 계산합니다. 그런 다음 해시 값은 테이블의 슬롯을 제공합니다. 보통 mod( hash, table size ). 이것도 O (1)입니다.

이것이 일반적인 해결책입니다. 두 개의 숫자 계산을 통해 임의의 개체를 키로 사용하여 임의의 개체를 값으로 사용했습니다. 이만큼 빠를 수있는 것은 거의 없습니다.

객체에서 해시 값으로의 변환은 이러한 일반적인 방법 중 하나로 발생합니다.

1. 4 바이트의 "기본"객체 인 경우 객체의 기본 값은 숫자입니다.

2. 개체의 주소는 4 바이트이며 개체의 주소는 해시 값으로 사용할 수 있습니다.

3. 간단한 해시 함수 (MD5, SHA1 등)는 개체의 바이트를 누적하여 4 바이트 숫자를 만듭니다. 고급 해시는 단순한 바이트 합계가 아니며 단순한 합계는 모든 원래 입력 비트를 충분히 반영하지 않습니다.

해시 테이블의 슬롯은 mod (number, size of table)입니다.

해당 슬롯에 원하는 값이 있으면 완료된 것입니다. 원하는 값이 아니라면 다른 곳을 찾아야합니다. 테이블에서 빈 자리를 찾는 데 널리 사용되는 몇 가지 프로빙 알고리즘이 있습니다. 선형은 다음 자유 지점에 대한 간단한 검색입니다. Quadratic은 빈 슬롯을 찾는 비선형 호핑입니다. 난수 생성기 (고정 시드 포함)를 사용하여 데이터를 균등하지만 임의로 분산하는 일련의 프로브를 생성 할 수 있습니다.

프로빙 알고리즘은 O 가 아닙니다 (1). 테이블이 충분히 크면 충돌 확률이 낮고 프로브는 중요하지 않습니다. 테이블이 너무 작 으면 충돌이 발생하고 프로빙이 발생합니다. 이 시점에서 성능 최적화를 위해 프로빙과 테이블 크기의 균형을 맞추는 것은 "조정 및 조정"의 문제가됩니다. 보통 우리는 테이블을 더 크게 만듭니다.

해시 테이블을 참조하십시오 .

---

아직 특별히 언급하지 않은 것 :

배열에 대해 해시 테이블을 사용하는 요점은 성능입니다.

배열을 반복하는 것은 일반적으로 O (1)에서 O (x)까지 어디든 걸릴 수 있습니다. 여기서 x는 배열의 항목 수입니다. 그러나 배열에서 수십만 개의 항목에 대해 이야기하는 경우 항목을 찾는 시간은 매우 가변적 입니다.

적절하게 가중 된 해시 테이블은 일반적으로 해시 테이블 에있는 항목의 수에 관계없이 거의 일정한 액세스 시간이 O (1)을 약간 넘습니다.

---

무작위로 생성 된 100 개의 숫자에 해시 테이블을 사용하고 싶지 않을 것입니다.

해시 테이블에 대해 생각하는 좋은 방법은 값 쌍에 대해 생각하는 것입니다. 학생을 사용하고 모든 사람이 학생 ID 번호를 가지고 있다고합시다. 프로그램에서 학생에 대한 정보 (이름, 전화 번호, 청구서 등)를 저장합니다. 기본 정보 (예 : 이름 또는 학생 ID) 만 사용하여 학생에 대한 모든 정보를 찾으려고합니다.

학생이 10,000 명이라고 가정 해 보겠습니다. 모든 항목을 배열에 저장하면 각 항목의 학생 ID를 찾고있는 항목과 비교하여 전체 배열을 반복해야합니다.

대신 학생 ID 번호를 배열의 위치로 "해시"(아래 참조)하면 번호가 동일한 해시를 가진 학생의 학생 만 검색하면됩니다. 원하는 것을 찾는 데 훨씬 적은 노력이 필요합니다.

이 예에서 학생 ID가 6 자리 숫자라고 가정 해 보겠습니다. 우리의 해시 함수는 "해시 키"로 숫자의 맨 아래 3 자리 만 사용할 수 있습니다. 따라서 232145는 배열 위치 145로 해시됩니다. 따라서 999 요소의 배열 만 필요합니다 (각 요소는 학생 ​​목록 임).

그것은 당신에게 좋은 시작이 될 것입니다. 물론 이런 종류의 정보에 대해서는 교과서 나 위키피디아를 읽어야합니다. 그러나 나는 당신이 이미 그것을했고 독서에 지쳐 있다고 가정합니다.

---

간단히 말해 해시 테이블이 작동하는 방식입니다.

책으로 가득 찬 도서관이 있다고 상상해보십시오. 책을 배열로 보관하는 경우 각 책을 선반의 한 지점에 놓고 누군가가 책을 찾도록 요청하면 모든 선반을 살펴 보게됩니다. 누군가 "책 # 12345"라고 말하면 꽤 쉽게 찾을 수 있습니다.

대신 책 제목이 'A'로 시작하면 1 행에 간다고 가정 해 봅시다. 두 번째 문자가 'B'이면 1 행, 랙 2에갑니다. 세 번째 문자가 'C'이면 책 위치를 식별 할 때까지 행 1, 랙 2, 선반 3 ... 등으로 이동합니다. 그러면 책 제목에 따라 정확히 어디에 있어야하는지 알 수 있습니다.

이제 제가 설명한 단순한 "해싱"알고리즘에는 몇 가지 문제가 있습니다. 일부 선반은 과부하 상태이고 다른 선반은 비어 있고 일부 책은 동일한 슬롯에 할당됩니다. 따라서 실제 해시 함수는 신중하게 구성됩니다. 그러한 문제를 피하십시오.

그러나 이것이 기본 아이디어입니다.

---

해시 테이블과 배열의 차이점에 대해 그 부분에 대답하겠습니다 ...하지만 이전에 가져 오기의 해싱 알고리즘을 구현 한 적이 없기 때문에 더 많은 지식을 가진 사람에게 맡기겠습니다. :)

배열은 정렬 된 객체 목록입니다. 객체 자체는별로 중요하지 않습니다. 중요한 것은 삽입 순서대로 객체를 나열하려는 경우 항상 동일하다는 것입니다 (즉, 첫 번째 요소 의 인덱스는 항상 0입니다).

해시 테이블은 순서가 아닌 키로 색인이 생성됩니다. 해싱 알고리즘에 대한 기본 검색이 제가 할 수있는 것보다 훨씬 더 많은 통찰력을 제공 할 것이라고 생각합니다. 위키피디아는 매우 괜찮은 정보를 제공합니다. "키로 사용되는 임의의 개체에 대한 빠른 검색을 위해 키가 들어갑니다.

장점 : 삽입 순서가 중요한 경우 배열 또는 정렬 된 목록이 필요합니다. 임의의 키 (다양한 해시 기능으로 입력)를 통한 빠른 조회가 중요하다면 해시 테이블이 의미가 있습니다.

---

[위 me.yahoo.com/a의 댓글에 대한 답변입니다.]

그것은 해시 함수에 따라 다릅니다. 해시 함수가 단어 길이에 따라 단어를 해시한다고 가정 해 봅시다. chris의 키는 5가됩니다. 마찬가지로 yahoo의 키도 5가됩니다. 5로 키가있는 '버킷'에서). 이렇게하면 데이터 크기와 동일한 배열을 만들 필요가 없습니다.

---

제 생각에이 질문은 지금까지 매우 명확하고 다양한 방식으로 대답됩니다.

다른 관점을 추가하고 싶습니다 (새로운 독자도 혼동 할 수 있음)

최소한의 추상화 수준에서 배열은 연속적인 메모리 블록입니다. 시작 주소 ( startAddress), 크기 ( sizeOfElement) 및 index단일 요소의가 주어지면 요소의 주소는 다음과 같이 계산됩니다.

elementAddress = startAddress + sizeOfElement * index

여기서 주목해야 할 흥미로운 점은 배열이 O (1)index 에서 값의 위치를 ​​계산하는 해시 함수로 키와 위의 함수를 사용하여 해시 테이블로 추상화 /보기 할 수 있다는 것 입니다.

---

해시 테이블은 빠른 조회를 위해 생성 된 데이터 구조입니다.

항목 수가 매우 적 으면 해시 테이블이 효과적이지 않습니다.

참고

몇 가지 예 :

    import java.util.Collection;
    import java.util.Enumeration;
    import java.util.Hashtable;
    import java.util.Set;

    public class HashtableDemo {

    public static void main(String args[]) {

// Creating Hashtable for example

     Hashtable companies = new Hashtable();


// Java Hashtable example to put object into Hashtable
// put(key, value) is used to insert object into map

     companies.put("Google", "United States");
     companies.put("Nokia", "Finland");
     companies.put("Sony", "Japan");


// Java Hashtable example to get Object from Hashtable
// get(key) method is used to retrieve Objects from Hashtable

     companies.get("Google");


// Hashtable containsKey Example
// Use containsKey(Object) method to check if an Object exits as key in
// hashtable

     System.out.println("Does hashtable contains Google as key: "+companies.containsKey("Google"));


// Hashtable containsValue Example
// just like containsKey(), containsValue returns true if hashtable
// contains specified object as value

      System.out.println("Does hashtable contains Japan as value: "+companies.containsValue("Japan"));


// Hashtable enumeration Example
// hashtabl.elements() return enumeration of all hashtable values

      Enumeration enumeration = companies.elements();

      while (enumeration.hasMoreElements()) {
      System.out.println("hashtable values: "+enumeration.nextElement());
      }


// How to check if Hashtable is empty in Java
// use isEmpty method of hashtable to check emptiness of hashtable in
// Java

       System.out.println("Is companies hashtable empty: "+companies.isEmpty());


// How to find size of Hashtable in Java
// use hashtable.size() method to find size of hashtable in Java

      System.out.println("Size of hashtable in Java: " + companies.size());


// How to get all values form hashtable in Java
// you can use keySet() method to get a Set of all the keys of hashtable
// in Java

      Set hashtableKeys = companies.keySet();


// you can also get enumeration of all keys by using method keys()

      Enumeration hashtableKeysEnum = companies.keys();


// How to get all keys from hashtable in Java
// There are two ways to get all values form hashtalbe first by using
// Enumeration and second getting values ad Collection

      Enumeration hashtableValuesEnum = companies.elements();


      Collection hashtableValues = companies.values();


// Hashtable clear example
// by using clear() we can reuse an existing hashtable, it clears all
// mappings.

       companies.clear();
      }
     }

산출:

Does hashtable contains Google as key: true

Does hashtable contains Japan as value: true

hashtable values: Finland

hashtable values: United States

hashtable values: Japan

Is companies hashtable empty: false

Size of hashtable in Java: 3

참조 URL : https://stackoverflow.com/questions/282712/the-fundamentals-of-hash-tables