11장 해시테이블

  • 해시 테이블은 키-값 쌍을 기반으로 자료를 얻을 수 있다
  • 해시 테이블에는 put()과 get()의 두 함수가 있어 자료를 저장하고 얻어올 수 있다
  • localStorage는 해시 테이블에 기반한 자료구조로 모든 브라우저가 지원하는 기본 자바스크립트 객체이다
  • 해시 테이블에서 가장 중요한건 해시 함수로 이 함수는 특정 키를 자료를 저장하는 배열의 인덱스로 변환한다
  • 좋은 해시 함수는 동일한 키는 동일한 해시값을 생성해야 하며(결정성), 시간 복잡도는 O(1)이어야 하며(효율성) 배열 전체를 최대한 활용해야 한다(균일한 분배)
  • 해싱의 첫번째 기법은 소수를 사용하는 것 이다
  • 소수에 의한 모듈러는 고정된 크기에 대해 가장 균등한 분배를 보장한다
  • 소수 모듈러로 나눈 나머지 값으로 인덱싱하는 해시 테이블에서 같은 값이 있다면 충돌이 일어나게 되는데 이를 회피하기 위하여 탐사 해싱 기법을 이용한다
  • 선형 탐사는 만약 같은 키로 해싱된다면 그 다음 빈 곳을 찾아 해싱한다
  • 이 때 get(key)함수를 사용한다면 충돌된 부분을 찾은 후에 해당 값을 찾고자 테이블을 순회한다
  • 이차 탐사는 선형 탐사와는 달리 1씩 증가시키지 않고 완전 제곱을 사용하여 사용 가능한 인덱스에 키를 균등하게 분배한다
  • 이차 해싱 함수를 사용해 원래 해싱 함수로부터 나온 결과를 한 번 더 해싱하면 키를 균일하게 분배할 수 있다
  • 해시 테이블 구현 (교재에는 옛날 방식으로 구현되어 있어서 class 문법을 사용하였음)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    class HashTable {
        constructor(size) {
          this.size = size;
          this.keys = this.initArray(size);
          this.values = this.initArray(size);
          this.limit = 0;
        }
      
        put(key, value) {
          if (this.limit >= this.size) 
            throw 'hash table is full';
      
            let hashedIndex = this.hash(key);
      
            while (this.keys[hashedIndex] != null) {
              hashedIndex++
              hashedIndex = hashedIndex % this.size;
            }
          this.keys[hashedIndex] = key;
          this.values[hashedIndex] = value;
          this.limit++
        }
        
        get(key) {
          let hashedIndex = this.hash(key);
      
          while (this.keys[hashedIndex] != key) {
              hashedIndex++
              hashedIndex = hashedIndex % this.size;
          }
          return this.value[hashedIndex];
        }
        
        hash(key) {
          if(!Number.isInteger(key)) 
            throw 'must be number';
          return key % this.size;
        }
      
        initArray(size) {
          return Array.from({length: size}, () => null);
        }
    }
  • 이차 탐사 사용하기
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    class HashTable {
        constructor(size) {
          this.size = size;
          this.keys = this.initArray(size);
          this.values = this.initArray(size);
          this.limit = 0;
        }
      
        put(key, value) {
          if (this.limit >= this.size) 
            throw 'hash table is full';
      
            let hashedIndex = this.hash(key);
      
            while (this.keys[hashedIndex] != null) {
              hashedIndex++
              hashedIndex = hashedIndex % this.size;
            }
          this.keys[hashedIndex] = key;
          this.values[hashedIndex] = value;
          this.limit++
        }
        
        get(key) {
          let hashedIndex = this.hash(key);
      
          while (this.keys[hashedIndex] != key) {
              hashedIndex++
              hashedIndex = hashedIndex % this.size;
          }
          return this.value[hashedIndex];
        }
        
        hash(key) {
          if(!Number.isInteger(key)) 
            throw 'must be number';
          return key % this.size;
        }
      
        initArray(size) {
          return Array.from({length: size}, () => null);
        }
    }
  • 이차 탐사 (put, get 함수만)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    put(key, value) {
      if (this.limit >= this.size) 
        throw 'hash table is full';
      
      let hashedIndex = this.hash(key), squareIndex = 1;
      
      while (this.keys[hashedIndex % this.size] != null) {
        hashedIndex += Math.pow(squareIndex, 2);
        squareIndex++;
      }
      this.keys[hashedIndex % this.size] = key
      this.value[hashedIndex % this.size] = value;
      this.limit++
    }
        
    get(key) {
      let hashedIndex = this.hash(key);
      
      while (this.keys[hashedIndex] != key) {
        hashedIndex++
        hashedIndex = hashedIndex % this.size;
      }
      return this.value[hashedIndex];
    }
  • 선형 탐사를 활용한 이중 해싱
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    put(key, value) {
      if (this.limit >= this.size) 
        throw 'hash table is full';
      
      let hashedIndex = this.hash(key);
      
      while (this.keys[hashedIndex] != null) {
        hashedIndex++;
        hashedIndex = hashedIndex % this.size;
      }
      this.keys[hashedIndex] = key
      this.value[hashedIndex] = value;
      this.limit++
    }
        
    get(key) {
      let hashedIndex = this.hash(key);
      
      while (this.keys[hashedIndex] != key) {
        hashedIndex++
        hashedIndex = hashedIndex % this.size;
      }
      return this.value[hashedIndex];
    }

    hash(key) {
      if (!Number.isInteger(key)) 
        throw 'must be number'
      return this.secondHash(key);
    }

    secondHash(hashedKey) {
      let R = this.size - 2;
      return R - hashedKey % R;
    }
  • 해시테이블은 크기가 처음에 정의되는(size를 매개변수로 생성자에 전달한 것을 보자) 고정된 크기의 자료구조이다
  • 해시 함수를 사용해 균등하게 분배하고 충돌이 일어나는 것을 최대한 막아야한다

12장 스택과 큐

  • 스택은 마지막에 삽입된 항목만을 제거하고 접근할 수 있다
  • 자바스크립트에서 배열에는 스택 클래스를 정의한 pop과 push라는 메서드가 있다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Stack {
      constructor (arr) {
        this.arr = [];
        if(arr) this.arr = arr;
      }

      getBuffer() {
        return this.arr.slice();
      }

      isEmpty() {
        return this.arr.length === 0;
      }

      peek() {
        return this.arr[this.arr.length-1];
      }

      push(value) {
        this.arr.push(value);
      }

      pop() {
        return this.arr.pop();
      }
    }
  • 위에서부터 n번째 노드에 접근하기 위해 pop을 n번 호출해야 한다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    const stackAccessNthTopNode = (stack, n) => {
      let bufferArr = stack.getBuffer();
      if (n <= 0) throw 'error';

      let bufferStack = new Stack(bufferArr);

      while(--n! === 0) 
        bufferStack.pop();

      return bufferStack.pop();
    }
  • 검색 또한 이와 비슷한 방식으로 구현할 수 있다
    1
    2
    3
    4
    5
    6
    7
    8
    const stackSearch = (stack, element) => {
      let bufferArr = stack.getBuffer();
      let bufferStack = new Stack(bufferArr);
      while(!bufferStack.isEmpty()){
        if (bufferStack.pop() === element) return true;
      }
      return false;
    }
  • 큐는 스택과 달리 첫번째로 추가도니 항목만을 제거할 수 있는 자료 구조이다
  • 자바스크립트에서는 shift()와 push()라는 메서드가 있어 이 함수를 호출하면 배열의 첫번째 항목을 제거해 리턴한다
  • 큐에 추가하는 것을 인큐(enqueuing)라고, 제거하는 것을 디큐(dequeuing)라 한다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Queue {
      constructor (arr) {
        this.arr = [];
        if(arr) this.arr = arr;
      }

      getBuffer() {
        return this.arr.slice();
      }

      isEmpty() {
        return this.arr.length === 0;
      }

      peek() {
        return this.arr[0]; // 제거하지 않고 값만 리턴
      }

      enqueue(value) {
        return this.arr.push(value);
      }

      dequeue() {
        return this.arr.shift();
      }
    }
  • 큐에 접근할 때엔 인덱스로 접근할 수 없다 n번째 노드에 접근하려면 디큐를 n번 호출해야 한다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    const queueAccessNthTopNode = (queue, n) => {
      let bufferArr = queue.getBuffer();
      if (n <= 0) throw 'error'

      let bufferQueue = new Queue(bufferArr);

      while(--n !== 0) 
        bufferQueue.dequeue(); // 필요한 노드 직전까지 디큐

      return bufferQueue.dequeue(); // 리턴으로 디큐하면 해당 노드가 필요한 노드
    }
  • 스택을 사용해 큐를 구현하기
    → 두개의 스택을 사용한다면 큐를 만들 수 있다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class TwoStackQueue {
      constructor() {
        this.inbox = new Stack();
        this.outbox = new Stack();
      }

      enqueue(value) {
        this.inbox.push(value);
      }

      dequeue() {
        if(this.outbox.isEmpty()) {
          while(!this.inbox.isEmpty()){
            this.outbox.push(this.inbox.pop());
          }
        }
        return this.outbox.pop();
      }
    }
  • 큐를 사용해 스택을 구현하기도 마찬가지로 두 개의 큐를 사용하면 스택을 구현할 수 있다
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class QueueStack {
      constructor() {
        this.inbox = new Queue();
      }

      push(value) {
        this.inbox.enqueue(value);
      }

      pop() {
        let size = this.inbox.arr.length - 1;
        let cnt = 0;
        let bufferQueue = new Queue();
        while(++counter <= size)
          bufferQueue.enqueue(this.inbox.dequeue());
        let popped = this.inbox.dequeue();
        this.inbox = bufferQueue;
        return popped;
      }
    }
  • 고객 객체를 매개변수로 받아 선입선출(Queue) 방식으로 음식을 주문 처리하는 점원 클래스를 설계
    1. 점원은 주문을 위해 고객의 이름과 주문 항목을 요구
    2. 첫번째로 받은 주문을 먼저 처리함
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      class Customer {
        constructor (name, order) {
          this.name = name;
          this.order = order;
        }

        addOrder (customer) {
          this.customers.enqueue(customer);
        }

        deliverOrder() {
          let finishedCustomer = this.customers.dequeue();
        }
      }

      function Cashier() {
        this.customers = new Queue();
      }
  • 스택을 사용해 괄호 검증기를 설계하기
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    const BracketVerification = string => {
      let stack = new Stack();
      for (let pos = 0; pos < string.length; pos++) {
        let currentChar = string.charAt(pos);
        if(currentChar === "("){
          stack.push(currentChar);
        } else if (currentChar ===")") {
          if(stack.isEmpty()) return false;
          stack.pop();
        }
      }
      return stack.isEmpty();
    }
  • 정렬 가능한 스택 설계하기
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class sortableStack {
      constructor (size) {
        this.size = size;
        this.mainStack = new Stack();
        this.sortedStack = new Stack();
        for (let i = 0; i < this.size; i++) {
          this.mainStack.push(Math.floor(Math.random() * 11));
        }
      }

      sortStackDescending() {
        while(!this.mainStack.isEmpty()){
          let temp = this.mainStack.pop();
          while(!this.sortedStack.isEmpty && this.sortedStack.peek() <temp) {
            this.mainStack.push(this.sortedStack.pop());
          }
          this.sortedStack.push(temp)
        }
      }
    }