해시 테이블의 기본은 무엇입니까?

https://stackoverflow.com/questions/282712

08-07-2019
|

문제

나는 해시 테이블의 기본 개념에 대해 상당히 혼란스러워합니다.해시를 코딩하려면 어떻게 시작해야 할까요?해시 테이블과 일반 배열의 차이점은 무엇입니까?

기본적으로 누군가가 이 질문에 대답한다면 내 모든 질문에 대한 답이 나올 것이라고 생각합니다.무작위로 생성된 100개의 숫자(키)가 있는 경우 해시 테이블을 어떻게 구현하고 이것이 배열보다 유리한 이유는 무엇입니까?

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

해결책

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

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

해시 테이블과 배열은 데이터를 저장하고 검색 할 수있는 구조입니다. 둘 다 당신이 지정할 수 있습니다 인덱스 그리고 그것과 관련된 값을 검색합니다. Daniel Spiewak이 지적한 바와 같이 차이점은 배열의 지수가 잇달아 일어나는, 해시 테이블의 것들이 데이터의 가치 그들과 관련이 있습니다.

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

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

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

문제 없어요. 가장 간단한 방법은 데이터에서 수행 할 수있는 임의의 수학적 작업을 발명하는 것입니다. 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의 계수로 줄였습니다!

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

다른 팁

먼저 해시 기능이 무엇인지 이해해야합니다. 해시 함수는 키 (예 : arbritary 길이의 스트링)를 취하고 숫자를 반환하는 함수입니다. 가능한 한 독특합니다. 동일한 키는 항상 동일한 해시를 반환해야합니다. 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

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

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.

나는 이것이 대부분의 질문에 대답 할 것이라고 생각합니다. 해시 테이블의 구현은 상당히 흥미로운 주제입니다. 어떤 Wikipedia 주소가 지나갈 수 있습니다.

"해시 테이블이 키를 찾는 방식과 키가 어떻게 생성되는지에 더 관심이 있습니다."

해싱은 핵심 개체를 숫자로 변환합니다. 이것을 "해싱"이라고합니다. 객체에서 해시를 만듭니다. 보다 해시 기능. 예를 들어 문자열의 바이트를 합산하는 것은 표준 해시 기술입니다. Sum Modulo 2를 계산합니다³² 해시를 관리 가능한 크기로 유지합니다. 해시는 항상 같은 대답을합니다. 이것은 영형(1).
숫자는 해시 가능에 "슬롯"을 제공합니다. 임의의 키 객체가 주어지면 해시 값은 해시 값을 계산합니다. 해시 값은 테이블에있는 슬롯을 제공합니다. 대개 mod( hash, table size ). 이것은 영형(1), 또한.

그것이 일반적인 해결책입니다. 두 개의 숫자 계산과 임의의 객체에서 값으로 임의의 객체의 키로 임의의 객체에서 갔다. 빠른 것은 거의 없습니다.

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

4 바이트의 "원시"객체 인 경우 객체의 기본 값은 숫자입니다.
객체의 주소는 4 바이트이고 객체의 주소는 해시 값으로 사용할 수 있습니다.
간단한 해시 기능 (MD5, SHA1, 무엇이든) 객체의 바이트를 축적하여 4 바이트 번호를 만듭니다. 고급 해시는 단순한 바이트 합계가 아니며 간단한 합계는 모든 원래 입력 비트를 상당히 반영하지는 않습니다.

해시 테이블의 슬롯은 모드 (숫자, 크기)입니다.

해당 슬롯에 원하는 값이 있으면 완료됩니다. 그것이 원하는 값이 아니라면 다른 곳을 봐야합니다. 테이블에서 무료 지점을 찾을 수있는 몇 가지 인기있는 프로브 알고리즘이 있습니다. 선형은 다음 자유 지점에 대한 간단한 검색입니다. 2 차는 무료 슬롯을 찾는 비선형 호핑입니다. 임의의 숫자 생성기 (고정 시드 포함)를 사용하여 데이터를 골고루이지만 임의로 전파하는 일련의 프로브를 생성 할 수 있습니다.

프로브 알고리즘은 아닙니다 영형(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'인 경우, It. 책 위치를 식별 할 때까지 1 행, 랙 2, 선반 3 등으로 이동합니다. 그런 다음 책의 제목을 바탕으로 책이 어디에 있어야하는지 정확히 알 수 있습니다.

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

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

해시 테이블과 배열의 차이점에 대해 그 부분에 대답하겠습니다. 그러나 나는 이전에 어떤 수입의 해싱 알고리즘을 구현 한 적이 없기 때문에, 나는 그것을 누군가에게 더 잘 알고 있습니다 :)

배열은 순서 대상 객체 목록 일뿐입니다. 객체 자체는 실제로 중요하지 않습니다 ... 중요한 것은 삽입 순서 대상으로 객체를 나열하려면 항상 동일하다는 것입니다 (첫 번째 요소가 의미하는 것입니다. 언제나 인덱스가 0)입니다.

해시 테이블은 순서가 아닌 키로 인덱싱됩니다 ... 해싱 알고리즘에 대한 기본 검색은 내가 할 수있는 것보다 훨씬 더 많은 통찰력을 줄 것이라고 생각합니다 ... Wikipedia는 매우 괜찮은 것입니다 ... "버킷을 결정하는" "키는 키로 사용되는 임의의 객체를 빠르게 검색하기 위해 키가 들어갑니다.

장점에 관해서는 : 삽입 순서가 중요하다면 배열 또는 주문 된 목록이 필요합니다. 임의의 키 (다양한 해시 함수에 의해 키)에 의해 빠르게 조회되는 것이 중요하다면 해시 테이블이 의미가 있습니다.

이것은 위의 댓글에 대한 답변입니다. yahoo.com/a 위

해시 기능에 따라 다릅니다. 해시 함수가 단어의 길이에 따라 단어를 해시한다고 가정하자, Chris의 핵심은 5가 될 것입니다. 마찬가지로 Yahoo의 키도 5가됩니다. '버킷'에서 5로 키가 듭니다). 이렇게하면 데이터 크기와 동일한 배열을 만들 필요가 없습니다.

내 생각에 이 질문은 지금쯤 아주 분명하고 다양한 방법으로 답이 나올 것 같습니다.

나는 또 다른 관점을 추가하고 싶습니다(새로운 독자에게도 혼란을 줄 수 있음).

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

elementAddress = startAddress + sizeOfElement * index

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

해시 테이블은 빠른 조회를 위해 만들어진 데이터 구조입니다.

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

참조

몇 가지 예 :

    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

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow