자바스크립트 해시란 무엇인가

자바스크립트에서 해시는 해시 테이블을 말하며, 해시 테이블을 통해 키워드를 기반으로 메모리 저장 위치에 직접 접근하는 데이터 구조로, 데이터 요소의 저장 위치와 키워드 사이에 일정한 관계가 설정됩니다. 데이터 요소와 해당 관계를 설정하는 함수를 해시 함수라고 합니다.

이 튜토리얼의 운영 환경: Windows 7 시스템, JavaScript 버전 1.8.5, Dell G3 컴퓨터.

자바스크립트 해시의 기본 개념:

해시 테이블(해시 테이블)은 해시 테이블을 통해 데이터 요소의 저장 위치와 위치를 기반으로 메모리 저장 위치에 직접 접근하는 데이터 구조입니다. 데이터 요소의 키워드 간에는 일정한 대응 관계가 설정되며, 이러한 대응 관계를 설정하는 함수를 해시 함수라고 합니다.

해시 테이블 구성 방법:

저장할 데이터 요소의 수를 n이라고 가정하고 길이가 m(m>n)인 연속 저장 단위를 설정하고 각각의 키워드 Ki( 데이터 요소) 0

수학적 관점에서 해시 함수는 실제로 키워드를 메모리 단위로 매핑하는 것이므로, 해시 함수로 계산된 Huaxi 주소가 가능한 가장 간단한 연산을 통해 최대한 균일하게 위치에 매핑될 수 있기를 바랍니다. 일련의 메모리 단위에서 해시 함수를 구성하는 데에는 세 가지 핵심 사항이 있습니다. (1) 해시 테이블의 삽입 및 검색 효율성을 향상시키기 위해 작업 프로세스가 최대한 간단하고 효율적이어야 합니다. 함수는 좋은 해시 유형을 가져야 합니다. 해시 충돌 가능성을 줄이려면 셋째, 해시 함수는 메모리를 절약하기 위해 더 큰 압축을 가져야 합니다.

일반적으로 사용되는 방법:

• 직접 주소 방법: 키워드의 특정 선형 함수 값을 해시 주소로 사용합니다. 이는 hash(K)=aK+C로 표현될 수 있으며 충돌이 없다는 장점이 있습니다. 하지만 단점은 공간 복잡도가 더 높을 수 있어 요소 수가 적은 경우에 적합합니다.
• 나누기 방법: 데이터 요소 키워드를 특정 상수로 나누어 남겨지는 해시 주소입니다. 이 방법은 계산이 간단하고 널리 사용되는 해시 함수입니다.
  hash(K=K mod C; 이 방법의 핵심은 상수를 선택하는 것입니다. 일반적인 요구 사항은 해시 테이블 자체의 길이에 가깝거나 같다는 것입니다. 연구 이론에 따르면 상수는 소수를 선택할 때 가장 잘 작동합니다
• 디지털 분석 방법: 이 방법은 데이터 요소 키워드에서 비교적 균일한 값을 갖는 일부 숫자를 해시 주소로 사용하는 것입니다. 이렇게 하면 충돌을 최대한 피할 수 있지만 이 방법은 모든 키워드가 알려진 상황에만 적합합니다. 더 일반적인 해시 테이블은 적용되지 않습니다.
• 제곱합 방법: 현재 문자열을 유니코드 값으로 변환하고 이 값의 제곱을 찾습니다. 제곱된 값의 자릿수는 현재 숫자의 해시 값입니다. 구체적으로 비트 수는 현재 해시 테이블의 크기에 따라 다릅니다.
• 분할 합 방법: 삽입할 값을 개수에 따라 여러 세그먼트로 나눕니다. 현재 해시 테이블의 자릿수에 세그먼트를 추가하고 결과의 가장 높은 비트를 버립니다.

해시 충돌 해결 방법:

해시 테이블을 구성할 때 다음이 있습니다. 문제: 두 개의 서로 다른 키워드에 대해 해시 주소는 해시 함수에 의해 계산됩니다. 동일한 해시 주소를 얻었을 때 이 현상을 해시 충돌이라고 부릅니다.

해시 충돌은 주로 두 가지 요인과 관련이 있습니다

(1 ) 채움 인자(Filling Factor), 해시 테이블에 저장된 데이터 요소 수와 해시 주소 공간의 비율, a=n/m이 작을수록 충돌 가능성이 작아집니다. 반대로 충돌 가능성은 더 커지지만, a가 클수록 공간 활용도는 작아집니다. 일반적으로 0.6-0.9 사이에서 제어되지만 .net의 HashTable은 a의 최대값을 0.72로 직접 정의합니다. (Microsoft의 공식 MSDN에서는 HashTable의 기본 채우기 요소가 1.0이라고 나와 있지만 실제로는 0.72의 배수입니다.)
(2) 해시 함수가 적절하다면 해시 주소를 해시 주소 공간에 최대한 균등하게 분산시켜 충돌 발생을 줄일 수 있지만, 좋은 해시 함수를 획득하는 것은 크게 좌우됩니다. 많이 연습하세요

1) 공개 주소 지정 방법

Hi=(H(key) + di) MOD m i=1,2,…k(k 여기서 H(key)는 해시입니다. 함수, m은 해시 테이블의 길이입니다. di는 증분 시퀀스입니다. 3개의 증분 시퀀스가 ​​있습니다.
①선형 감지 후 해싱: di=1,2,3,…,m-1
②2차 감지 후 해싱: di=1^2,-12,2 ^2,-2 2,…±k^2(k ③의사 난수 검출 후 해싱: di=의사 난수 시퀀스

단점:

테이블의 i, i+1, i+2 위치에 이미 레코드가 채워져 있으면 다음 해시 주소가 i, i+1, i+2, i+인 레코드가 생성되는 현상을 볼 수 있습니다. 3개가 모두 i+3의 위치가 채워지게 됩니다. 충돌 처리 과정에서 발생하는, 첫 번째 해시 주소가 다른 두 개의 레코드가 동일한 후속 해시 주소를 놓고 경쟁하는 현상을 '2차 집계', 즉 동의어 처리 시에 말합니다. 충돌 프로세스에는 동의어가 아닌 충돌이 추가됩니다. 그러나 반면 선형 감지를 사용하고 충돌을 처리하기 위해 해싱을 사용하면 해시 테이블이 가득 차지 않는 한 충돌하지 않는 주소 Hk를 항상 찾을 수 있다는 것을 보장할 수 있습니다. 2차 감지 및 재해싱은 해시 테이블 길이 m이 4j+3(j는 정수) 형식의 소수인 경우에만 가능합니다. 즉, 개방형 주소 지정 방식은 2차 집계를 발생시켜 검색에 해를 끼칩니다.

2) 재해시 방법

Hi = RHi(키), i=1,2,...k RHi는 모두 다른 해시 함수, 즉 동의어가 주소 충돌을 일으킬 때 다른 해시의 주소 충돌이 발생하지 않을 때까지 함수가 계산됩니다. 이 방법은 집계 가능성이 낮지만 계산 시간이 늘어납니다.

단점: 계산 시간이 늘어납니다.

3) 체인 주소 방식(zipper 방식)

키워드가 동의어인 모든 레코드를 동일한 선형 연결 리스트에 저장합니다.

장점:

①지퍼 방식은 충돌 처리가 간단하고 누적 현상이 없습니다. 즉, 동의어가 아닌 단어는 절대 충돌하지 않으므로 평균 검색 길이가 더 짧습니다.
지퍼 방식은 동적으로 적용되므로 테이블을 생성하기 전에 테이블 길이를 결정할 수 없는 상황에 더 적합합니다.
③ 오픈 어드레싱 방식은 충돌을 줄이기 위해 채우기 요소 α가 작아야 하므로 노드가 크기가 크면 공간이 많이 낭비됩니다. 지퍼 방식에서는 α ≥ 1이 허용되며 노드가 큰 경우 지퍼 방식에서 추가된 포인터 도메인은 무시할 수 있으므로 공간이 절약됩니다.
④ 지퍼 방식으로 구성된 해시 테이블에서 노드 삭제 작업; 구현하기 쉽습니다. 연결리스트에서 해당 노드를 삭제하면 됩니다. 오픈 주소 방식으로 구축된 해시 테이블의 경우, 노드를 삭제한다고 해서 단순히 삭제된 노드의 공간을 비워둘 수는 없으며, 그렇지 않으면 해시 테이블 이후에 채워지는 동의어 노드의 검색 경로가 잘려지게 된다. 이는 다양한 오픈 주소 방식에서 빈 주소 단위(즉, 오픈 주소)가 검색 ​​실패의 조건이기 때문입니다. 따라서 충돌을 처리하기 위해 공개 주소 방식을 사용하는 해시 테이블에 대해 삭제 작업을 수행할 때 삭제된 노드를 삭제 표시만 할 수 있을 뿐 실제로 노드를 삭제할 수는 없습니다.

단점:

지퍼 방식의 단점은 포인터에 추가 공간이 필요하다는 것입니다. 따라서 노드 크기가 작은 경우 저장된 포인터 공간을 사용하여 크기를 확장하면 개방형 주소 지정 방식이 공간을 더 절약합니다. 필팩터(Fill Factor)가 작아지면 오픈 어드레싱 방식의 충돌이 줄어들어 평균 탐색 속도가 빨라진다.

4) 공개 오버플로 영역 설정

해시 함수의 값 범위가 [0,m-1]이라고 가정하고 벡터 HashTable[0...m-1]을 기본으로 둡니다. 테이블, 각 구성 요소는 하나의 레코드로 저장되고 OverTable[0...v] 벡터를 오버플로 테이블로 설정합니다. 해시 함수로 얻은 해시 주소와 상관없이 키워드가 기본 테이블의 키워드와 동의어인 모든 레코드는 충돌이 발생할 경우 오버플로 테이블에 채워집니다.

충돌 처리가 없는 간단한 해시 함수의 해시 테이블 구현

class Hash {
  constructor() {
    this.table = new Array(1024);
  }
  hash(data) {
    //就将字符串中的每个字符的ASCLL码值相加起来，再对数组的长度取余
    var total = 0;
    for (var i = 0; i < data.length; i++) {
      total += data.charCodeAt(i);
    }
    console.log("Hash Value: " + data + " -> " + total);
    return total % this.table.length;
  }
  insert(key, val) {
    var pos = this.hash(key);
    this.table[pos] = val;
  }
  get(key) {
    var pos = this.hash(key);
    return this.table[pos]
  }
  show() {
    for (var i = 0; i < this.table.length; i++) {
      if (this.table[i] != undefined) {
        console.log(i + ":" + this.table[i]);
      }
    }
  }
}
var someNames = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
var hash = new Hash();
for (var i = 0; i < someNames.length; ++i) {
  hash.insert(someNames[i], someNames[i]);
}

hash.show();

정사각형 중간 단계 방법을 사용하여 해시 함수를 구성하고 개방 주소 방법 선형 감지 방법을 사용하여 충돌을 해결합니다.

class Hash {
  constructor() {
    this.table = new Array(1000);
  }
  hash(data) {
    var total = 0;
    for (var i = 0; i < data.length; i++) {
      total += data.charCodeAt(i);
    }
    //把字符串转化为字符用来求和之后进行平方运算
    var s = total * total + ""
    //保留中间2位
    var index = s.charAt(s.length / 2 - 1) * 10 + s.charAt(s.length / 2) * 1
    console.log("Hash Value: " + data + " -> " + index);
    return index;
  }
  solveClash(index, value) {
    var table = this.table
    //进行线性开放地址法解决冲突
    for (var i = 0; index + i < 1000; i++) {
      if (table[index + i] == null) {
        table[index + i] = value;
        break;
      }
    }
  }
  insert(key, val) {
    var index = this.hash(key);
    //把取中当做哈希表中索引
    if (this.table[index] == null) {
      this.table[index] = val;
    } else {
      this.solveClash(index, val);
    }
  }
  get(key) {
    var pos = this.hash(key);
    return this.table[pos]
  }
  show() {
    for (var i = 0; i < this.table.length; i++) {
      if (this.table[i] != undefined) {
        console.log(i + ":" + this.table[i]);
      }
    }
  }
}
var someNames = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
var hash = new Hash();
for (var i = 0; i < someNames.length; ++i) {
  hash.insert(someNames[i], someNames[i]);
}

hash.show();

【추천 학습: javascript 고급 튜토리얼】

위 내용은 자바스크립트 해시란 무엇인가의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!