JaeHyung

Just Do It

3 분 소요

해시 구현

구현

  • 해시 테이블 크기, 해시 함수를 정해야 함
  • Load factor: 원소의 개수/테이블의 크기
  • Load factor를 작게 유지하면 충돌이 덜 생겨서 각 연산이 거의 O(1)에 동작하지만 cache hit rate가 줄어들고 메모리도 많이 차지하는 단점이 있음
  • Chaining에서는 load factor를 1이하가 되게 하고 Open addressing에서는 0.75이하로 둠
  • 테이블의 크기가 소수이면 좋음
  • 정수에 대한 해시 함수 
    // 정수에 대한 해시 함수
const int M=1000003;
int my_hash(int x){
  return (M+x%M)%M; //음수에 대해서도 가능
}
  • 문자열에 대한 해시 함수 
    // 문자열에 대한 해시 함수(비효율)
const int M=1000003;
int my_hash(string& s){
  int h=0;
  for(auto x: s){
      h+=x;   //간단하지만 치명적(충돌이 빈번하게 발생해서 좋지 않은 해시 함수)
  }
  return h%M;
}
// 문자열에 대한 해시 함수(효율)
// rolling hash라는 방법 사용
// ex) my_hash("abc")=('a'*1000^2 + 'b'*1000^1 + 'c'*1000^0)%M
const int M=1000003;
const int a =1000;
int my_hash(string& s){
  int h=0;
  for(auto x: s){
      h=(h*a+x)%M;
  }
  return h%M;
}

    구현(Chaining)

    #include<iostream>
#include<cassert>
using namespace std;
const int M = 1000003; //테이블의 크기를 의미
const int a = 1000;
const int MX = 500005; //최대 삽입 횟수
int head[M]; //각 M개의 연결 리스트에 대해 시작주소를 의미
int pre[MX]; // 연결리스트에서 이전 값 의미
int nxt[MX]; // 연결리스트에서 다음 값 의미
string key[MX];
int val[MX];
int unused=0;
int my_hash(string& s){
  int h=0;
  for(auto x:s){
      h=(h*a+x)%M;
  }
  return h;
}
//key[idx] == k인 idx를 반환, 만약 k가 존재하지 않을 경우 -1을 반환
//키에 대응되는 값을 반환하는게 아니라 인데그를 반환함에 주의
int find(string k){
  int h=my_hash(k);
  int idx=head[h];
  while(idx!=-1){
      if(key[idx]==k){
          return idx;
      }
      idx=nxt[idx];
  }
  return -1;
}
void insert(string k,int v){
  int idx=find(k);
  if(idx!=-1){
      val[idx]=v;
      return;
  }
  int h=my_hash(k);
  key[unused]=k;
  val[unused]=v;
  if(head[h]!=-1){
      nxt[unused]=head[h];
      pre[head[h]]=unused;
  }
  head[h]=unused;
  unused++;
}
void erase(string k){
  int idx=find(k);
  if(idx==-1){
      return;
  }
  if(pre[idx]!=-1){
      nxt[pre[idx]]=nxt[idx];
  }
  if(nxt[idx]!=-1){
      pre[nxt[idx]]=pre[idx];
  }
  int h=my_hash(k);
  if(head[h]==idx){
      head[h]=nxt[idx];
  }
}
void test(){
  insert("orange", 724); // ("orange", 724)
  insert("melon", 20); // ("orange", 724), ("melon", 20)
  assert(val[find("melon")] == 20);
  insert("banana", 52); // ("orange", 724), ("melon", 20), ("banana", 52)
  insert("cherry", 27); // ("orange", 724), ("melon", 20), ("banana", 52), ("cherry", 27)
  insert("orange", 100); // ("orange", 100), ("melon", 20), ("banana", 52), ("cherry", 27)
  assert(val[find("banana")] == 52);
  assert(val[find("orange")] == 100);
  erase("wrong_fruit"); // ("orange", 100), ("melon", 20), ("banana", 52), ("cherry", 27)
  erase("orange"); // ("melon", 20), ("banana", 52), ("cherry", 27)
  assert(find("orange") == -1);
  erase("orange"); // ("melon", 20), ("banana", 52), ("cherry", 27)
  insert("orange", 15); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15)
  assert(val[find("orange")] == 15);
  insert("apple", 36); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15), ("apple", 36)
  insert("lemon", 6); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15), ("apple", 36), ("lemon", 6)
  insert("orange", 701);  // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 701), ("apple", 36), ("lemon", 6)
  assert(val[find("cherry")] == 27);
  erase("xxxxxxx");
  assert(find("xxxxxxx") == -1);
  assert(val[find("apple")] == 36);
  assert(val[find("melon")] == 20);
  assert(val[find("banana")] == 52);
  assert(val[find("cherry")] == 27);
  assert(val[find("orange")] == 701);
  assert(val[find("lemon")] == 6);  
  cout << "good!\n";  
}
int main(void){
  fill(head,head+M,-1);
  fill(pre,pre+MX,-1);
  fill(nxt,nxt+MX,-1);
  test();
  return 0;
}

    Open Addressing

    #include<iostream>
#include<cassert>
using namespace std;
const int M = 1000003; //테이블의 크기를 의미
const int a = 1000;
const int EMPTY = -1; // 비어있음
const int OCCUPY = 0; // 칸에 값이 있음
const int DUMMY = 1; // 칸에 값이 있었다가 삭제됨
int status[M]; // EMPTY / OCCUPY / DUMMY
string key[M];
int val[M];
int my_hash(string& s){
  int h=0;
  for(auto x:s){
      h=(h*a+x)%M;
  }
  return h;
}
//key[idx] == k인 idx를 반환, 만약 k가 존재하지 않을 경우 -1을 반환
//키에 대응되는 값을 반환하는게 아니라 인데그를 반환함에 주의
int find(string k){
  int idx=my_hash(k);
  while(status[idx]!=EMPTY){
      if(status[idx]==OCCUPY && key[idx]==k){
          return idx;
      }
      idx=(idx+1) %M;
  }
  return -1;
}
void insert(string k,int v){
  int idx=find(k);
  if(idx!=-1){
      val[idx]=v;
      return;
  }
  idx=my_hash(k);
  while(status[idx]==OCCUPY){
      idx=(idx+1)%M;
  }
  key[idx]=k;
  val[idx]=v;
  status[idx]=OCCUPY;
}
void erase(string k){
  int idx=find(k);
  if(idx!=-1){
      status[idx]=DUMMY;
  }
}
void test(){
  insert("orange", 724); // ("orange", 724)
  insert("melon", 20); // ("orange", 724), ("melon", 20)
  assert(val[find("melon")] == 20);
  insert("banana", 52); // ("orange", 724), ("melon", 20), ("banana", 52)
  insert("cherry", 27); // ("orange", 724), ("melon", 20), ("banana", 52), ("cherry", 27)
  insert("orange", 100); // ("orange", 100), ("melon", 20), ("banana", 52), ("cherry", 27)
  assert(val[find("banana")] == 52);
  assert(val[find("orange")] == 100);
  erase("wrong_fruit"); // ("orange", 100), ("melon", 20), ("banana", 52), ("cherry", 27)
  erase("orange"); // ("melon", 20), ("banana", 52), ("cherry", 27)
  assert(find("orange") == -1);
  erase("orange"); // ("melon", 20), ("banana", 52), ("cherry", 27)
  insert("orange", 15); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15)
  assert(val[find("orange")] == 15);
  insert("apple", 36); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15), ("apple", 36)
  insert("lemon", 6); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15), ("apple", 36), ("lemon", 6)
  insert("orange", 701);  // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 701), ("apple", 36), ("lemon", 6)
  assert(val[find("cherry")] == 27);
  erase("xxxxxxx");
  assert(find("xxxxxxx") == -1);
  assert(val[find("apple")] == 36);
  assert(val[find("melon")] == 20);
  assert(val[find("banana")] == 52);
  assert(val[find("cherry")] == 27);
  assert(val[find("orange")] == 701);
  assert(val[find("lemon")] == 6);  
  cout << "good!\n";  
}
int main(void){
  fill(status,status+M,EMPTY);
  test();
  return 0;
}

참고

그래프

1 분 소요

그래프 정의 그래프: 정점과 간선으로 이루어진 자료구조 차수(degree): 각 정점에 대해서 간선으로 연결된 이웃한 정점의 개수 무방향 그래프(Undirected Graph): 간선의 방향이 없는 그래프 방향 그래프(Directed Graph): 간선의 방향이 있...

우선순위 큐

최대 1 분 소요

우선순위 큐 정의와 성질 우선순위 큐: pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐 원소의 추가(Heap): O(lgN) 우선순위가 가장 높은 원소의 확인(Heap): O(1) 우선순위가 가장 높은 원소 제거(Heap...

이진 검색 트리

1 분 소요

이진 검색 트리 정의와 성질 정점(Vertex/Node): 트리에서 각 원소 루트(Root): 트리에서 가장 꼭대기의 정점 리프(leaf): 제일 말단에 위치해 자식이 없는 정점 간선(Edge): 정점을 연결하는 선 이진 트리(Binary Tree): 각 노드의...

해시

1 분 소요

해시 정의와 성질 해시에서는 insert, erase, find, update 모두 O(1) 해시 함수: 임의의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수 충돌 서로 다른 키가 같은 해시 값을 가질 경우 충돌이 일어남 충돌이 발생했을 때 회...