Set

jjunn0·2020년 4월 15일
0

Set는 array나 list 처럼 순열 자료구조 (collection) 입니다.
하지만 set는 순서라는 개념이 존재하지 않습니다. Set의 특징은 다음과 같습니다.

데이터를 비순차적(unordered)으로 저장할 수 있는 순열 자료구조 (collection) 입니다.
삽입(insertion) 순서대로 저장되지 않는다. 즉 특정한 순서를 기대할 수 없는 자료구조입니다.
수정 가능합니다.(mutable).
동일한 값을 여러번 삽입 불가능합니다. 동일한 값이 여러번 삽입 되면 하나의 값만 저장됩니다.
Fast Lookup이 필요할때 주로 쓰입니다.

Array와 달리 set은 요소들을 순차적으로 저장하지 않습니다.
Set에서 요소들이 저장될 때 순서는 다음과 같습니다.
저장할 요소의 값의 hash 값을 구합니다.
해쉬값에 해당하는 공간(bucket)에 값을 저장합니다.
이렇게 set는 저장하고자 하는 값의 해쉬값에 해당하는 bucket에 값을 저장하기 때문에 순서가 없습니다. 순서가 없기 때문에 indexing도 없습니다.
그리고 해쉬값 기반의 bucket에 저장하기 때문에 중복된 값을 저장할 수 없습니다.
해쉬값을 기반으로 저장하기 때문에 look up 이 굉장히 빠릅니다. 🏊
Look up: 특정 값을 포함하고 있는지를 확인 하는것 ==> 5 in my_set
Set의 총 길이와 상관없이 단순히 해쉬값 계산 후 해당 bucket을 확인하면 됨으로 O(1)

class MySet {
  // constructor는 수정하지 말것!
  constructor(size) {
    this.size = size;
    this.bucket = [];
    for(var i =0;i<this.size;i++){
      this.bucket[i] = 0;
    }
  }

  // values 함수는 수정하지 말것!
  values(){
    var all_data = ""
    var cs_data = ""
    for(var i =0; i<this.size; i++){
      if(this.bucket[i] !== 0){
        all_data += this.bucket[i];
        all_data += ", "
      }
    }
    if(all_data.charAt(all_data.length-1) === " "){
      cs_data = all_data.slice(0,-2);
    }
    return cs_data;
  }

  hash_value(key){
    let crypto = require('crypto')
    let shasum = crypto.createHash('sha1');
    const shasumHex = shasum.update(key).digest('hex').replace(/[^0-9]/g,"").slice(0,3);
    return shasumHex%this.size;
    // 1번 문제 구현
  }
  
  add(key){
    let hash = this.hash_value(key);
    if (this.bucket[hash] !== 0) {
      for ( let i = hash+1; i <= this.size; i++ ) {
        if (this.bucket[i] === 0) {
          this.bucket[i] = key;
          return
        }
      }
    } else {
      this.bucket[hash] = key;
    }
    return this.bucket;
    // 2번 문제 구현
  }
}

const myset = new MySet(15);

console.log("wecode hash value = " + myset.hash_value('wecode'));
console.log("wework hash value = " + myset.hash_value('wework'));
console.log("weplay hash value = " + myset.hash_value('weplay'));
console.log("wedevelop hash value = " + myset.hash_value('wedevelop'));
console.log("wespace hash value = " + myset.hash_value('wespace'));

myset.add('wecode');
myset.add('wework');
myset.add('weplay');
myset.add('wedevelop');
myset.add('wespace');
console.log("bucket = " + myset.values());

생성자로 사이즈를 지정해 주고, 다 0으로 초기화 시켜줍니다. python 예제는 none으로 초기화 시킵니다. 값을 add 통해 넣어주면 hash 값을 구한 후 숫자만 남겨두고 앞에서 3자리를 사이즈로 나눈 나머지 값을 구합니다. 사이즈로 나눈 나머지 값은 사이즈 보다 클 수 없으므로 사이즈 안에 다 들어가게 됩니다. 그리고, 그 값이 인덱스가 돼, 인덱스에 값이 들어가는데 만약 값이 있을 경우 빈 공간을 만날 때까지 옆으로 이동하게 됩니다. 진짜 이렇게 생기진 않았지만 이런식으로 작동 합니다.!

profile
서울로 상경해 매일매일 생존기를 찍고 있는 Front end 개발자 최준영입니다 🥰

0개의 댓글