JavaScript의 해시 테이블(해시 테이블)에 대한 자세한 소개(코드 예)

이 글은 자바스크립트의 해시 테이블(해시 테이블)에 대한 자세한 소개(코드 예제)를 제공합니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.

해시 테이블

해시 테이블(해시 테이블, 해시 테이블이라고도 함)은 키(Key)를 기준으로 메모리 저장 위치에 직접 접근하는 데이터 구조입니다. 즉, 필요한 쿼리 데이터를 테이블의 위치에 매핑하는 키 값에 대한 함수를 계산하여 레코드에 액세스하므로 조회 속도가 빨라집니다. 이 매핑 함수를 해시 함수라고 하며, 레코드를 저장하는 배열을 해시 테이블이라고 합니다.

위 그림부터 분석해 보겠습니다.

• 세트 U가 있는데, 이는 1000, 10, 152, 9733, 1555, 997, 1168

• 오른쪽에는 10- 슬롯 세트 목록(해시 테이블)을 사용하려면 세트 U의 정수를 이 목록에 저장해야 합니다.

• 저장 방법과 어떤 슬롯에 저장되나요? 이 문제는 해시 함수를 통해 해결해야 합니다. 제 저장 방법은 10의 나머지 부분을 가져가는 겁니다. 이 사진을 보시죠

• 1000%10=0, 10%10=0 그러면 두 개의 정수 1000과 10이 숫자 0에 저장됩니다 슬롯에

• 152%10=2, 그런 다음 슬롯 2

• 9733%10=3에 저장하고 슬롯 번호 3

위의 간단한 예를 통해 다음과 같이 해야 합니다. 다음 사항에 대해 전반적으로 이해하세요

• 집합 U는 해시 테이블에 나타날 수 있는 키입니다

• 해시 함수는 테이블에 키 값을 전달하기 위해 사용자가 직접 설계하는 방법입니다. set U through 특정 계산은 계산된 키

• 를 저장하는 예제의 나머지

해시 테이블과 같은 해시 테이블에 저장됩니다. 그런 다음 일반적으로 값을 어떻게 얻는지 살펴보겠습니다.

예를 들어 키가 1000이고 값이 '장산' ---> {key:1000, value:'Zhang San'}
위 설명에 따르면 1000에 저장되어야 할까요? 이 슬롯에는 %10이 있습니다.
키를 통해 Zhang San 값을 찾고 싶을 때, 키%10 슬롯에서만 검색하면 되나요? 이 시점에서 멈추고 생각할 수 있습니다.

해싱의 일부 용어(간단히 살펴볼 수 있음)

• 해시 테이블의 가능한 모든 키를 전체 집합이라고 합니다. U

• M을 사용하여 슬롯 수를 나타냅니다.

• 키 제공 해시 함수는 그것이 어느 슬롯에 나타나야 하는지 계산합니다. 위의 예에서 해시 함수 h=k%M, 해시 함수 h는 키 k에서 슬롯으로의 매핑입니다.

• 1000과 10이 모두 0번 슬롯에 저장되어 있습니다. 이런 상황을 충돌이라고 합니다.

이것을 보시고 해시함수에 대한 전반적인 이해가 되셨는지 모르겠습니다. 예제와 생각을 통해 다시 돌아가서 기사 상단에 있는 해시 테이블의 정의를 읽을 수 있습니다. 읽어보시면 이해가 되실 것 같습니다.

일반적으로 사용되는 해시 함수

정수 h=>k%M 처리(즉, 위에 제시한 예)

문자열 처리:

    function h_str(str,M){
        return [...str].reduce((hash,c)=>{
            hash = (31*hash + c.charCodeAt(0)) % M
        },0)
    }

해시 알고리즘은 여기서 초점이 아니므로 다루지 않았습니다. 아주 깊이 연구하려면, 여기서 가장 중요한 것은 해시 테이블이 어떤 종류의 데이터 구조인지, 어떤 장점이 있는지, 정확히 무엇을 하는지 이해하는 것입니다.
해시 함수는 특정 알고리즘을 통해 키를 목록에 매핑합니다.

해시 테이블 만들기

위 설명을 통해 간단한 해시 테이블을 만들어보겠습니다

해시 테이블의 구성

• M 슬롯

• 해시 함수가 있습니다

• 있습니다 add 메소드 해시 테이블에 키 값을 추가

• 삭제하는 삭제 메소드가 있습니다

• 키를 기준으로 해당 값을 찾는 검색 메소드가 있습니다

초기화

- 초기화 해시 테이블에는 몇 개의 슬롯이 있나요?
- 배열을 사용하여 M개의 슬롯을 생성하세요

    class HashTable {
        constructor(num=1000){
            this.M = num;
            this.slots = new Array(num);
        }
    }

해시 함수

문자열을 처리하는 해시 함수입니다.

여기에 먼저 전달하세요. 더 엄격하게 하려면 문자열을 배열로 변환하세요. 예를 들어 'abc' => ] => ['a','b','c ']

각 문자의 charCodeAt를 별도로 계산하세요. 나머지 M은 총 10개의 슬롯만 갖습니다. %10은 확실히 0-9

    h(str){
        str = str + '';
        return [...str].reduce((hash,c)=>{
            hash = (331 * hash + c.charCodeAt()) % this.M;
            return hash;
        },0)
    }

의 슬롯에 속할 것입니다

Add

해시 함수를 호출하여 해당 저장 주소(유추의 슬롯)를 얻습니다.

슬롯은 우리가 계산한 것과 같이 2차원 배열로 표현되어야 합니다. 슬롯 번호는 0(슬롯[0])이면 슬롯 번호가 슬롯[0][0]에 저장되어야 합니다. 나중에 들어오는 슬롯도 0번 슬롯이므로 슬롯[0][1]에 저장해야 합니다.

    add(key,value) {
        const h = this.h(key);
        // 判断这个槽是否是一个二维数组, 不是则创建二维数组
        if(!this.slots[h]){
            this.slots[h] = [];
        }
        // 将值添加到对应的槽中
        this.slots[h].push(value);
    }

Delete

해시 알고리즘을 통해 슬롯을 찾습니다

필터링을 통해 삭제

    delete(key){
        const h = this.h(key);
        this.slots[h] = this.slots[h].filter(item=>item.key!==key);
    }

Find

찾기 해시 알고리즘을 통해 해당 슬롯

찾기 기능을 사용하여 동일한 키의 값을 찾아보세요

해당 값을 반환합니다

    search(key){
        const h = this.h(key);
        const list = this.slots[h];
        const data = list.find(x=> x.key === key);
        return data ? data.value : null;    
    }

总结

讲到这里，散列表的数据结构已经讲完了，其实我们每学一种数据结构或算法的时候，不是去照搬实现的代码，我们要学到的是思想，比如说散列表它究竟做了什么，它是一种存储方式，可以快速的通过键去查找到对应的值。那么我们会思考，如果我们设计的槽少了，在同一个槽里存放了大量的数据，那么这个散列表它的搜索速度肯定是会大打折扣的，这种情况又应该用什么方式去解决，又或者是否用其他的数据结构的代替它。

补充一个小知识点

v8引擎中的数组 arr = [1,2,3,4,5] 或 new Array(100) 我们都知道它是开辟了一块连续的空间去存储，而arr = [] , arr[100000] = 10 这样的操作它是使用的散列，因为这种操作如果连续开辟100万个空间去存储一个值，那么显然是在浪费空间。

위 내용은 JavaScript의 해시 테이블(해시 테이블)에 대한 자세한 소개(코드 예)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!