[Algorithm] 해시 테이블(Hash Table) 해시함수(Hash Function)에서 문자열 키(key)값을 정수로 바꾸기

해시 테이블에서 문자열을 받았을 때 해싱하는 방법을 알아보자


환경 및 선수조건


String을 Key값으로 받았을 때

  • 1번의 방식은 단순하나 중복이 될 가능성이 크며 2~3번의 방식이 분포를 더 크게 만들 수 있다.
  • 만약 연산중에 혹은 결과 값이 해시 테이블의 크기보다 크다면 해시 테이블의 크기만큼 나누어서 나머지의 값을 취하면 된다.


1. 문자열에 있는 문자들을 모두 더하기

  • 문자열에 있는 문자들을 다 더해서 계산하는 방식
  • 단, 아래와 같은 경우에는 “abc”, “acb” 그리고 “cba”의 결과가 모두 같다는 단점이 있다. 즉 hashCode("abc")==hashCode("acb")==hashCode("cba")

int hashCode(String s){
	int r = 0;

	for(int i = 0; i < s.length(); i++){             
		 r += s[i];
	}

	return r;
}


2. 다항식을 이용해서 구하기

  • h(s) = xk-1 × ak-1 + xk-2 × ak-2 + ... + x0 × a0와 같은 다항식을 바탕으로 만드는 방식
  • 특정한 값 a(일반적으로 소수가 좋다고 한다.)를 곱하고 문자열에 있는 문자를 더하면서 완성해가는 방식

int hashCode(String s){
	int i;
	int r = 0;

	// Special Prime Number
	int a = 33;

	for(i = 0; i < s.length(); i++){
		 r += r*a + s[i];   
	}

	return r;
}


3. 시프트(Shift) 연산자를 이용해서 구하기

  • 위에 2번에 있는 다항식의 방법과 똑같은데 시프트(Shift)연산을 이용해서 값을 곱하는 방식

int hashCode(String s){
	int i;
	int r = 0;

	for(i = 0; i < s.length(); i++){
		 r += (r<<4) + s[i];   
	}

	return r;
}


참고자료

[Docker] 도커(Docker) 이미지 이름과 태그 목록 가져오기

> 도커(Docker) 이미지 이름과 태그 목록을 awk과 tail 명령어를 이용해 가져오는 방법을 알아보자## 환경- Linux 기반 시스템- Bash shell(/bin/bash)- Docker- awk, tail 명령어## 도커(Docker...… Continue reading