이 기사에서는 javascript에 대한 관련 지식을 제공합니다. JavaScript가 해시 테이블을 구현하는 방법에 대한 관련 문제를 주로 소개합니다. 최종 데이터가 삽입되는 배열의 전체 구조가 캡슐화되고, 그 결과는 해시 테이블입니다. 그것이 모두에게 도움이 되기를 바랍니다.
관련 권장 사항: javascript 학습 튜토리얼
해시 테이블은 일반적으로 배열을 기반으로 구현되지만 배열에 비해 많은 장점이 있습니다.
- 매우 빠른 삽입을 제공할 수 있습니다 - 삭제 조회
- 데이터가 아무리 많아도 삽입과 삭제에는 일정한 시간, 즉 O(1) 시간 수준에 가까운 시간이 필요합니다. 실제로 이를 수행하려면 몇 가지 기계 명령어만 필요합니다.
- 해시 테이블은 트리보다 빠르며 기본적으로 원하는 요소를 즉시 찾을 수 있습니다.
- 해시 테이블은 트리보다 코딩하기가 훨씬 쉽습니다
배열에 비해 해시 테이블의 몇 가지 단점:
- 데이터 해시 테이블의 순서가 잘못되어 요소를 고정된 방식으로 탐색할 수 없습니다
- 일반적으로 해시 테이블의 키는 반복될 수 없으며 동일한 키를 배치할 수 없으며 다른 요소를 저장하는 데 사용됩니다
- 공간 활용도가 높지 않고, 맨 아래 레이어는 배열을 사용하고, 일부 셀은 사용하지 않습니다
해시 테이블이란 무엇인가요?
- 해시 테이블은 구조와 원리를 그래픽 형태로 표현할 수 있는 배열, 연결 리스트, 트리와 달리 이해하기 쉽지 않습니다.
- 해시 테이블의 구조는 배열이지만 그 마법은 아래 첨자 값의 변환에 있습니다. 이 변환은 해시 함수 HashCode를 통해 얻을 수 있는 해시 함수라고 할 수 있습니다.
해시 테이블의 일부 개념
-
해시화: 큰 숫자를 배열 범위 내의 첨자로 변환하는 과정을 해싱이라고 합니다.
ha 해시 함수: - 우리는 보통 변환합니다 단어를 큰 숫자로 변환하고 해싱큰 숫자의 코드 구현을 해시 함수라는 함수에 넣습니다. 해시 테이블:
전체 - 구조를 배열로 캡슐화합니다. 최종 데이터가 삽입되고 그 결과는 해시 테이블입니다.
아직 해결해야 할 문제
:
해시된 첨자가 여전히
중복
가능합니다. 이 문제를 해결하는 방법은 무엇인가요? 이러한 상황을 - 갈등이라고 합니다. 갈등은 필연이며, 우리는 갈등을 해결할 수만 있습니다. 충돌 해결 방법
충돌 해결을 위한 두 가지 일반적인 솔루션:
옵션 1:
체인 주소 방법
(- Zip 방법) 아래 그림과 같이 각 번호를 지정합니다. 나머지 연산은
10
에서 수행되며, 나머지
0~9의 범위가 배열의 첨자 값으로 사용됩니다. 또한 배열의 각 첨자 값에 해당하는 위치는 더 이상 숫자를 저장하지 않고 나머지 연산 후 나머지가 동일한 숫자로 구성된 배열 또는 연결 목록을 저장합니다.
요약:
체인 주소 방식과의 충돌을 해결하는 방법은
각 배열 단위가 더 이상 단일 데이터를 저장하지 않고 체인을 저장하는 것입니다. 배열 또는 연결 목록, 두 데이터 구조는 검색 시 동일하게 효율적입니다(체인에는 일반적으로 요소가 너무 많지 않기 때문입니다). 옵션 2:
주소 열기 방법
; -
주소 열기 방법의 주요 작업 방법은
빈 셀을 찾아서
충돌하는 데이터 항목을 배치하는 것입니다. blank 블랭크 셀의 위치를 감지하는 다양한 방법으로, 그것은 세 가지 방법으로 나눌 수 있습니다. 충전 인자가 증가함에 따라 평균 감지 길이는 선형적으로 완만하게 증가합니다. 체인 주소 방식은 개발에 자주 사용됩니다. 예를 들어 체인 주소 방식은 Java의 HashMap에서 사용됩니다.
우수한 해시 함수
해시 테이블의 장점은 속도이기 때문에 고성능을 소모하는 복잡한 알고리즘을 사용할 수 없습니다. 속도를 향상시키는 한 가지 방법은 해시 함수에서
곱셈과 나눗셈
을 최소화하는 것입니다.
고성능 해시 함수에는 다음 두 가지 장점이 있어야 합니다. -
Horner의 법칙
: Horner의 법칙은 중국에서
Qin Jiu의 알고리즘이라고도 합니다. 언제 다항식의 값을 구하려면 먼저 가장 안쪽 괄호의 선형 다항식의 값을 계산한 다음 안쪽에서 바깥쪽으로 레이어별로 선형 다항식의 값을 계산합니다. 이 알고리즘은 n차 다항식 f(x)의 값을 n차 다항식의 값으로 변환합니다.
변환 전
:
곱셈 횟수: n (n+1)/2회; 덧셈 횟수: n회;
곱셈 횟수: n회 ; 추가 횟수: n회;
- 큰 O를 사용하여 시간 복잡도를 표현하는 경우
O(N2)- 에서
O(N)
으로 직접 감소됩니다. 균일한 분포해시 테이블에서 데이터가 균등하게 분포
되도록 하려면 상수를 사용
해야 할 때 소수를 사용해 보세요. 예: 해시 테이블의 길이, N번째 거듭제곱의 기초 등 Java의 HashMap은 체인 주소 방식을 사용하고 해싱 방식은 다음 공식을 사용합니다. index = HashCode (key) & (Length-1)
즉, 및 작업을 위해 데이터가 바이너리로 변환됩니다. 그리고 나머지 연산이 아닙니다. 이러한 방식으로 컴퓨터는 이진 데이터를 직접 작동하므로 더 효율적입니다. 그러나 JavaScript는 빅데이터라는 및
연산을 수행할 때 문제가 발생하므로 JavaScript를 사용하여 해싱을 구현할 때 나머지 연산이 계속 사용됩니다.
function HashTable() {
// 存放相关的元素
this.storage = [];
// 存了多少数据
this.count = 0;
// 用于标记数组中一共存放了多少个元素
this.limit = 7;
/*
设计哈希函数
①将字符串转成比较大的数字
②将大的数字hashCode压缩到数组范围之内
*/
HashTable.prototype.hashFunction = function (str, size) {
var hashCode = 0;
//秦九韶算法（霍纳算法）
// 哈希表的长度、N次幂的底数等尽量选取质数
for (var i = 0; i this.limit * 0.75) {
var newLimit = this.limit * 2;
var prime = this.getPrime(newLimit);
this.resize(prime);
}
};
// 获取
HashTable.prototype.get = function (key) {
var index = this.hashFunction(key, this.limit);
var bucket = this.storage[index];
if (bucket == null) return null;
for (var i = 0; i 7 && this.count 0 ? false : true;
};
// size
HashTable.prototype.size = function () {
return this.count;
};
// toString
HashTable.prototype.toString = function () {
var str = '';
for (var i = 0; i <strong></strong><strong></strong>관련 추천: javascript 학습 튜토리얼<p><javascript src="https://JavaScript%EA%B0%80%20%ED%95%B4%EC%8B%9C%20%ED%85%8C%EC%9D%B4%EB%B8%94%EC%9D%84%20%EA%B5%AC%ED%98%84%ED%95%98%EB%8A%94%20%EB%B0%A9%EB%B2%95%EC%97%90%20%EB%8C%80%ED%95%9C%20%EC%9E%90%EC%84%B8%ED%95%9C%20%EC%86%8C%EA%B0%9C.php.cn/upload/article/000/000/067/4ca10f86d3fe737c57c2ff0ae29c077f-3.png" alt="JavaScript가 해시 테이블을 구현하는 방법에 대한 자세한 소개"></javascript></p>로그인 후 복사
위 내용은 JavaScript가 해시 테이블을 구현하는 방법에 대한 자세한 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
