JavaScript가 해시 테이블을 구현하는 방법에 대한 자세한 소개
- WBOY앞으로
- 2022-03-03 17:21:052109검색
이 기사에서는 javascript에 대한 관련 지식을 제공합니다. JavaScript가 해시 테이블을 구현하는 방법에 대한 관련 문제를 주로 소개합니다. 최종 데이터가 삽입되는 배열의 전체 구조가 캡슐화되고, 그 결과는 해시 테이블입니다. 그것이 모두에게 도움이 되기를 바랍니다.
관련 권장 사항: javascript 학습 튜토리얼
해시 테이블은 일반적으로 배열을 기반으로 구현되지만 배열에 비해 많은 장점이 있습니다.
- 매우 빠른 삽입을 제공할 수 있습니다 - 삭제 조회
- 데이터가 아무리 많아도 삽입과 삭제에는 일정한 시간, 즉 O(1) 시간 수준에 가까운 시간이 필요합니다. 실제로 이를 수행하려면 몇 가지 기계 명령어만 필요합니다.
- 해시 테이블은 트리보다 빠르며 기본적으로 원하는 요소를 즉시 찾을 수 있습니다.
- 해시 테이블은 트리보다 코딩하기가 훨씬 쉽습니다
배열에 비해 해시 테이블의 몇 가지 단점:
- 데이터 해시 테이블의 순서가 잘못되어 요소를 고정된 방식으로 탐색할 수 없습니다
- 일반적으로 해시 테이블의 키는 반복될 수 없으며 동일한 키를 배치할 수 없으며 다른 요소를 저장하는 데 사용됩니다
- 공간 활용도가 높지 않고, 맨 아래 레이어는 배열을 사용하고, 일부 셀은 사용하지 않습니다
해시 테이블이란 무엇인가요?
- 해시 테이블은 구조와 원리를 그래픽 형태로 표현할 수 있는 배열, 연결 리스트, 트리와 달리 이해하기 쉽지 않습니다.
- 해시 테이블의 구조는 배열이지만 그 마법은 아래 첨자 값의 변환에 있습니다. 이 변환은 해시 함수 HashCode를 통해 얻을 수 있는 해시 함수라고 할 수 있습니다.
해시 테이블의 일부 개념
- 해시화: 큰 숫자를 배열 범위 내의 첨자로 변환하는 과정을 해싱이라고 합니다. ha 해시 함수:
- 우리는 보통 변환합니다 단어를 큰 숫자로 변환하고 해싱큰 숫자의 코드 구현을 해시 함수라는 함수에 넣습니다. 해시 테이블: 전체
- 구조를 배열로 캡슐화합니다. 최종 데이터가 삽입되고 그 결과는 해시 테이블입니다. 아직 해결해야 할 문제
해시된 첨자가 여전히
중복- 가능합니다. 이 문제를 해결하는 방법은 무엇인가요? 이러한 상황을
- 갈등이라고 합니다. 갈등은 필연이며, 우리는 갈등을 해결할 수만 있습니다. 충돌 해결 방법
충돌 해결을 위한 두 가지 일반적인 솔루션:
옵션 1:
체인 주소 방법- (
- Zip 방법) 아래 그림과 같이 각 번호를 지정합니다. 나머지 연산은 10
0~9의 범위가 배열의 첨자 값으로 사용됩니다. 또한 배열의 각 첨자 값에 해당하는 위치는 더 이상 숫자를 저장하지 않고 나머지 연산 후 나머지가 동일한 숫자로 구성된 배열 또는 연결 목록을 저장합니다.
각 배열 단위가 더 이상 단일 데이터를 저장하지 않고 체인을 저장하는 것입니다. 배열 또는 연결 목록, 두 데이터 구조는 검색 시 동일하게 효율적입니다(체인에는 일반적으로 요소가 너무 많지 않기 때문입니다). 옵션 2:
주소 열기 방법- ;
- 주소 열기 방법의 주요 작업 방법은 빈 셀을 찾아서
충돌하는 데이터 항목을 배치하는 것입니다. blank 블랭크 셀의 위치를 감지하는 다양한 방법으로, 그것은 세 가지 방법으로 나눌 수 있습니다. 충전 인자가 증가함에 따라 평균 감지 길이는 선형적으로 완만하게 증가합니다. 체인 주소 방식은 개발에 자주 사용됩니다. 예를 들어 체인 주소 방식은 Java의 HashMap에서 사용됩니다.
우수한 해시 함수을 최소화하는 것입니다.
- 고성능 해시 함수에는 다음 두 가지 장점이 있어야 합니다.
-
- 빠른 계산;
- 빠른 계산
: 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!