js 데이터 구조 - 산 목록

산 목록 을 사용 하 는 검색 알고리즘 은 두 단계 로 나 뉜 다. 1. 산 열 함 수 는 찾 은 키 를 배열 의 색인 으로 바 꿉 니 다.2. 충돌 처리 (지퍼 법 과 선형 탐지 법)
산열 함수
4. 567917. 정수, 나 누 기 남 는 방법: 크기 가 소수 M 인 배열 을 선택 하고 모든 정수 k 에 대해 k 나 누 기 M 의 여 수 를 계산한다
4. 567917. 부동 소수점, 키 가 0 에서 1 사이 의 실수 라면 우 리 는 그것 을 M 을 곱 하고 반올림 하여 0 에서 M - 1 사이 의 색인 값 을 얻 을 수 있 습 니 다
문자열
지퍼 기반 산 목록

class SeperateChainingHashST {
    constructor (M) {
        this.N = 0;//     
        this.M = M;//     
        this.st = [];
        for (let i = 0; i < M; i++){
            this.st[i] = new SequentialSearchST();
        }
    }
    hash (key) {
        return key%this.M;
    }
    put (key, value) {
        this.N++;
        this.st[this.hash(key)].put(key, value);
    }
    get (key) {
        return this.st[this.hash(key)].get(key);
    }
}
//      
class Node {
  constructor (key, value, next) {
    this.key = key;
    this.value = value;
    this.next = next;
  }
}
class SequentialSearchST {
  constructor () {
    this.first = null;
  }
  get (key) {
    let temp = this.first;
    while(temp && temp.key !== key) {
      temp = temp.next;
    }
    return temp && temp.value;
  }
  put (key, value){
    let temp = this.first;
    let prev =null;
    while(temp && temp.key !== key){
      prev = temp;
      temp = temp.next;
    }
    if(value !== undefined && temp == null ) {
      this.first = new Node(key, value, this.first);
      return;
    }
    if(value == undefined){
      if(prev === null){
        this.first =this.first && this.first.next;
      } else {
        prev.next = temp && temp.next;
      }
    }else{
      temp.value = value;
    }
  }
}

선형 탐지 법 에 기초 한 산 목록
주소 지정 클래스 의 산 목록 을 개방 하 는 핵심 사상 은 산 목록 의 빈 요 소 를 검색 이 끝 난 표지 로 하 는 것 입 니 다.

class LinearProbingHashST  {
    constructor (M) {
        this.N = 0;
        this.M = M;
        this.keys = [];
        this.value = [];
    }
    hash (key) {
        return key%this.M;
    }
    put (key, value) {
        if(this.N >= this.M/2) this.resize(2 * this.M);
        let i;
        for(i = this.hash(key); this.keys[i] != undefined; i = (i + 1)%this.M ) {
            if(this.keys[i] === key){
                this.value[i] = value;
                return ;
            }
        }
        this.N++;
        this.keys[i] = key;
        this.value[i] = value;      
    }
    get (key) {
        for(i = this.hash(key); this.keys[i] != undefined; i = (i + 1)%this.M ) {
            if(this.keys[i] === key){
                return this.value[i];
            }
        }
        return null;
    }
    delete (key) {
        if(this.get(key) === null) return;
        let i = key%this.M;
        while(this.keys[i] != key){
            i = (i+1)%this.M;
        }
        this.keys[i] = null;
        this.value[i] = null;
        i = (i+1)%this.M;
        while(this.keys[i] != null){
            let newKey = this.keys[i];
            let newValue = this.value[i];
            this.keys[i] = null;
            this.value[i] = null;
            this.N--;
            this.put(newKey, newValue);
            i = (i+1)%this.M;
        }
        this.N--;
        if(this.N > 0 && this.N <=Math.ceil(this.M/8)) this.resize(Math.ceil(this.M/2))
    }
    resize (M) {
        this.M = M;
        let oldKeys = this.keys;
        let oldValue = this.value;
        this.keys = [];
        this.value = [];
        this.N = 0;
        for(let i in oldKeys) {
            this.put(oldKeys[i], oldValue[i]);
        }
    }
}