해싱은 데이터를 최대한 빨리 저장하고 검색하는 데 널리 사용되는 기술입니다. 해싱을 사용하는 가장 큰 이유는 삽입, 삭제, 검색 등의 작업을 수행하기 때문입니다.

해싱을 사용하는 이유는 무엇입니까?

해싱에서는 삽입, 검색, 삭제와 같은 모든 작업을 O(1) 즉 상수 시간 내에 수행할 수 있습니다. 해싱의 최악의 경우 시간 복잡도는 여전히 O(n)이지만 평균 경우의 시간 복잡도는 O(1)입니다.

해시테이블

새로운 해시 테이블을 생성하기 위해 사용됩니다.

통사론:

// function to delete a key from the hashtable  delete (key) {  const index = this._setKey(key);  if (this.table[index]) {  this.table[index] = [];  this.size--;  return true;  } else {  return false;  } } 

구문을 사용한 기본 작업

얻다:

해시 테이블 내부의 키를 검색하고 해당 키와 연결된 값을 반환하는 데 사용됩니다.

통사론:

// function inside hashtable class to  // access a value using its key get(key) {  const target = this._setKey(key);  return this.table[target]; } 

끼워 넣다:

해시 테이블 내부에 새로운 키-값 쌍을 삽입하는 데 사용됩니다.

통사론:

// function to insert a value in the  // hash table using setKey function insert(value) {  const index = this._setKey(value);  this.table[index] = value;  this.size++; } 

찾다:

값을 검색하는 데 사용됩니다.

통사론:

// search a value (by getting its  // key using setKey function) search(value){  const index = this._setKey(value);  if(this.table[index]==value)  console.log('The value is found at index : ',index);  else  console.log('Not found'); } 

삭제:

해시 테이블에서 특정 키-값 쌍을 삭제하는 데 사용됩니다.

통사론:

// function to delete a key from the hashtable  delete (key) {  const index = this._setKey(key);  if (this.table[index]) {  this.table[index] = [];  this.size--;  return true;  } else {  return false;  } } 

Javascript의 해싱 구성 요소

1. 해시 테이블: 해시 테이블은 배열을 일반화한 것입니다. 필요한 경우 나중에 해당 항목을 쉽게 찾을 수 있도록 데이터 모음을 저장하는 기능을 제공합니다. 이렇게 하면 요소를 매우 효율적으로 검색할 수 있습니다.

2. 해시 함수: 해시 함수는 주어진 키를 특정 슬롯 인덱스로 변환하는 데 사용됩니다. 이는 가능한 모든 키를 고유 슬롯 인덱스에 매핑하는 데 사용됩니다. 모든 키가 고유한 슬롯 인덱스에 매핑되면 해시 함수를 완벽한 해시 함수라고 합니다. 완벽한 해시 함수를 만드는 것은 매우 어렵지만 프로그래머로서 우리의 임무는 충돌 횟수가 가능한 한 적은 해시 함수를 만드는 것입니다.

좋은 해시 함수에는 다음과 같은 속성이 있어야 합니다.

• 효율적으로 계산 가능합니다.
• 키를 균일하게 배포해야 합니다(각 테이블 위치는 각각 동일할 가능성이 있음).
• 충돌을 최소화해야 합니다.
• 로드 팩터(테이블의 항목 수를 테이블 크기로 나눈 값)가 낮아야 합니다.

3. 충돌 처리: 해시 함수는 큰 키에 대해 작은 숫자를 가져오므로 두 키가 동일한 값을 초래할 가능성이 있습니다. 새로 삽입된 키가 해시 테이블의 이미 점유된 슬롯에 매핑되는 상황을 충돌이라고 하며 일부 충돌 처리 기술을 사용하여 처리해야 합니다. 충돌을 처리하는 방법은 다음과 같습니다.

• 연결: 해시 테이블의 각 셀이 동일한 해시 함수 값을 가진 연결된 레코드 목록을 가리키도록 만드는 것이 아이디어입니다. 연결은 간단하지만 테이블 외부에 추가 메모리가 필요합니다.
• 공개 주소 지정: 개방형 주소 지정에서는 모든 요소가 해시 테이블 자체에 저장됩니다. 각 테이블 항목에는 레코드 또는 NIL이 포함됩니다. 요소를 검색할 때 원하는 요소를 찾거나 해당 요소가 테이블에 없다는 것이 분명해질 때까지 테이블 슬롯을 하나씩 검사합니다.

예시를 이용한 구현:

1 단계: 테이블 및 크기 초기 속성을 사용하여 HashTable 클래스를 만듭니다.

2 단계: 키를 인덱스로 변환하려면 비공개 setKey(key) 함수를 추가하세요.

3단계: 테이블에서 키-값 쌍을 추가하고 액세스하기 위한 insert() 및 get() 함수를 추가합니다.

4단계: 해시 테이블에서 키를 제거하려면 Remove() 함수를 추가하세요.

예시 1: 해시 테이블에 5개의 숫자 100,87,86,12,25 및 9를 저장해야 한다고 가정합니다. 이 경우 값을 인수로 사용하여 해시 테이블의 인덱스로 변환하는 setKey 함수를 생성합니다. 아래는 구현입니다.

자바스크립트

산출:

[ 100,  ,  12,  ,  86,  87,  ,  9 ] The value is found at index : 7 Not found [ 100,  ,  [],  ,  86,  87,  ,  9 ] 

출력에서 또는 테이블에 1~3개의 연속된 빈 공간/인덱스가 있음을 보여줍니다.

예시 2: 해시 테이블에 5인 가족의 연락처를 저장한다고 가정해 보겠습니다. 이를 위해 크기 10의 해시 테이블을 만들고 연락처 세부 정보를 저장합니다. 인덱스는 연락처 번호의 마지막 숫자를 해시 테이블의 인덱스로 변환하는 setKey 개인 함수를 사용하여 설정됩니다.

자바스크립트

산출:

[ ,  92752521,  98747512,  94755523,  ,  98754525,  ,  98556529 ] The contact number is found at index : 1 Contact Number not found [ ,  [],  98747512,  94755523,  ,  98754525,  ,  98556529 ] 

출력에서 또는 테이블에 1~3개의 연속된 빈 공간/인덱스가 있음을 보여줍니다.