• Lookup : 조회
  • 특정 원소가 컨테이너에 있는지 확인하거나 특정 키에 해당하는 값을 찾는 작업을 의미한다.
  • 사전에서 단어의 뜻을 찾는 다거나 특정 시설 출입 허가된 사람인지 체크 시 흔히 접할 수 있는 문제다.
• 조회를 매우 빠르기 수행할 수 있는 효과적인 알고리즘에 대해 학습한다.

해시 테이블

• 핵심은 hashing
  • 데이터를 가급적 고유한 숫자값으로 표현 후 같은 숫자값을 사용해 데이터 유무를 확인하거나 대응하는 원본 데이터를 추출한다.
  • 데이터에서 고유한 숫자 값을 계산하는 함수를 hash function이라고 한다.

Hashing

• 가장 간단한 방법은 bool type 배열을 하나 만들고, 입력 정수를 배열 원소의 인덱스로 취급하는 것이다.

  • data[x] = true 이런식으로 설정. 새 원소 삽입 시 해당 인덱스의 배열 값을 1로 설정하는 것이다.
    • 이렇게하면 특정 정수 x가 있는지 확인하려면 true인지 알면 된다.
  • 시간복잡도 O(1)

• 하지만 문제가 발생할 수 있다.

  • 데이터가 실수인 경우
  • 데이터가 숫자가 아닌 경우
  • 데이터 범위가 너무 큰 경우

• 위 문제 해결을 위해 어떤 Type의 값이든 원하는 범위의 정수로 매핑하는 function을 만들 수 있다. (hashing function)

  • 데이터 원소를 인자로 받아 정해진 범위의 정수를 반환

• 가장 간단한 hashing function은 나머지를 반환하는 modulo function이 있다. (% 연산)

  • (x % n)의 연산 결과를 반환하며 이는 0 ~ (n-1) 사이 정수만 나온다.
  • x를 (x % n) 위치에 삽입
  • hashing function을 통해 반환되는 숫자 값을 hash value라고한다.

• 하지만 (9 % 7), (16 % 7) 모두 2를 반환한다. 여기에 9가 들어갔는지, 16이 들어갔는지 모른다 ! 해당 x가 아니라 다른 값이 들어있을 수 있다는 것이다. 이런 현상을 collision이라한다.

  • 충돌(collision)이란 hash function이 서로 다른 키에 대해 같은 hash value를 반환해서 다수의 key가 같은 값을 같게되는 현상을 말한다.

해시 테이블에서 충돌

• 다수의 키를 저장할 수 없는 문제를 해결하고, 해시 테이블에 모든 키를 저장할 수 있는 몇 가지 방법에 대해 알아본다.

Chaining

• 해시 값이 같은 두 값을 모두 저장할 수 있는 방법 중 하나다.
  • 테이블의 특정 위치에서 하나의 키를 저장하는 것이 아닌 하나의 연결 리스트를 저장한다.
  • 새로 삽입된 키에 의해 충돌이 발생하면 리스트의 맨 뒤에 새로운 키를 추가한다. (배열이 아니라 연결 리스트를 사용하는 것은 특정 위치 원소를 빠르게 삭제하기 위함이다.)

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

using uint = unsigned int;

class hash_map
{
	std::vector<std::list<int>> data;
    
public:
	hash_map(sizt_t n)
    {
    	data.resize(n);
	}
    
    void insert(uint value)
    {
    	//  value 값을 항상 hash map(data vector)에 추가
    	int n = data.size();
        data[vaue % n].push_back(value);
        std::cout << value << "삽입" << std::endl;
	}
    
    bool find(uint value)
    {
    	// 특정 원소가 해시 맵에 있는지 확인하는 look-up function
    	int n = data.size();
        auto& entries = data[value % n];
        return std::find(entries.begin(), entries.end(), value) != entries.end();
	}
    
    void erase(uint value)
    {
    	int n = data.size();
        auto& entries = data[value % n];
        auto iter = std::find(entries.begin(), entries.end(), value);
        
        if (iter != entries.end())
        {
        	entries.erase(iter);
		}
	}
};

• list로 다수의 값을 저장하여 값을 덮어쓰는 현상이 발생하지 않는다.
• 삽입 함수의 시간 복잡도는 O(1)
  • 살짝 느린 상수 복잡도, 이점으로 무시할 수 있는 정도
• 저장할 key 개수에 비해 hash table이 너무 작으면 충돌이 자주 발생해서 리스트는 평균적으로 길어진다.
  • 메모리 낭비 발생 -> hash table 크기도 중요한 값이 된다.
• 부하율(load factor) : 해시 테이블에서 각각 리스트에 저장되는 key의 평균 개수
  • 전체 key 개수 / hash table size
  • 부하율 = 1 : 매우 이상적인 상태
  • 부하율 < 1 : 리스트 당 키가 하나도 저장되지 않은 경우가 있다는 것을 의미한다. 메모리 낭비
  • 부하율 > 1 : 리스트 평균 길이가 1보다 크다는 것이고 이 경우 검색, 삭제 등의 함수가 약간 느리게 동작할 여지가 있다.
• 몇몇 해시 테이블은 부하율은 O(1)로 계산할 수 있으므로 부하율 threshold를 1 근방 값으로 잡고 너무 크거나 작아지면 해시 함수를 변경하도록 구현되어있다. 이를 rehashing이라 한다.
  • 변경된 해시 함수에 의한 값의 분포와 부하율을 고려하여 해시 테이블의 크기도 변경할 수 있다.
• 항상 부하율이 해시 테이블 성능을 결정하는 지표는 아니다. 해시 테이블에 일곱개 원소가 저장되어있고, 테이블 사이즈가 7이라면 1로 부하율이 나오지만 하나의 버킷에 모든 원소가 저장되어있므녀 검색 연산이 O(N)이 발생하게된다.

Open addressing

• 체이닝과 다르게 모든 원소를 해시 테이블 내부에 저장하는 방식

  • 해시 테이블 크기가 반드시 데이터 개수보다 커야한다.

• 선형 탐색

  • 특정 해시 값에서 충돌 시 해당 위치에서 하나씩 다음 cell 위치로 이동하며 cell이 비어있는지 확인하고 비어있으면 원소를 삽입한다.
  • if hash(x) is not None -> hash(x + 1) -> hash(x + 2) ...
  • 원소 검색 시 해시 함수에서 반환 위치가 시작 위치를 가리키면, 해시 테이블 cluster의 맨 마지막 위치까지 선형 검색하는 경우가 발생할 수 있어 검색 속도가 크게 느려질 수 있다.
  • 특정 위치 clustering 문제 : 특정 해시 값이 너무 자주 발생해 데이터가 몇 개 group으로 뭉치는 형태로 저장되는 문제

• 이차함수 탐색(quadratic probing)

  • if hash(x) is not None -> hash((x+1)^2) -> hash((x+2)^2) ...
  • 군집 현상이 일어날 확률이 줄어들 뿐이지 근본적 해결은 되지 않는다.
    • 위치에 다른 값이 있느냐에 영향을 계속 받음.

cuckoo hashing

• 제대로만 구현한다면 O(1)의 시간 복잡도를 만족한다.
• 두 해시 테이블을 사용하고, 서로 다른 해시 함수를 갖는다.
  • 원소가 두 해시 테이블 중 어디든 저장될 수 있다.
  • 원소가 나중에 다른 위치로 이동할 수 있다.
• 룩업의 경우 두 해시테이블만 확인하면 되므로 O(1)
• 삽입 연산은 좀 더 걸릴 수 있다.
  • A 삽입 위치 탐색 -> 해당 위치에 다른 원소 B 저장 -> 해당 위치에 A 저장 후 B를 두 번째 해시 테이블로 이동 -> 두 번째 해시 테이블에 원소 C가 저장되어있다면 C를 첫 번째 해시 테이블로 옮기고, B를 저장
    • 완전히 비어있는 Cell이 나타날 때까지 재귀적으로 반복한다.
    • Cycle 발생 시, 무한 루프에 빠질 수 있다.
      - 순환이 발생했다면, 재해싱을 수행한다.

C++ Hash Table

• std::hash<stdd::string>(std::string) 함수 객체를 제공
  • 해시 함수 알고리즘이 내부적으로 구현되어있다.
• std::unordered_set<key>, std::unordered_map<key, value> 형태로 템플릿 형태로 바꿔 모든 데이터 타입에 대해 사용할 수 있는 해시 테이블을 제공한다.
• 해시 테이블의 각 행은 key, value 쌍을 저장하는 벡터로 구현할 수 있다.
  • 각 행을 bucket이라 한다.

#include <iostream>
#include <unordered_map>
#include <unordered_set>

void find(const std::unordered_map<int>& container, const int element)
{
	if (container.find(element) == container.end())
    	std::cout << element << " serach fail " << std::endl;
    else
    	std::cout << element << " search success " << std::endl;
}

void find(const std::unordered_map<int, int>& container, const int element)
{
	auto it = container.find(element);
    if (it == container.end())
    	std::cout << element << " search fail " << std::endl;
	else
    	std::cout << element << " search success " << it->second << std::endl;

• find 함수 사용법

int main()
{
	std::unordered_set<int> set = {1, 2, 3, 4, 5};
    set.insert(2);
    
    find(set, 4);
    set.erase(2);
    
    std::unordered_map<int, int> squareMap;
    
    squareMap.insert({2, 4});
    squareMap[3] = 9; // insert
    
    find(squareMap, 10);

• bench marking을 보면, std::unordered_set, std::unoredered_map이 list, vector, deque 보다 더 빠르게 동작한다.
• unordered_map의 [] 연산자는 값에대한 참조를 반환하므로 이를 이용해 저장된 값을 변경할수도 있다.
  • 해당 키가 없다면, 해당 위치에 기본값을 추가하여 반환 (int로 했으면 0)
• unordered_set, map은 모두 중복된 키를 허용하지 않는다.
  • std::unordered_multiset, multimap을 사용해야한다.
    • 위 두 컨테이너의 삽입 함수는 주어진 키가 이미 존재하는지 검사하지 않는다.
    • 특정 키에 해당하는 모든 값을 얻을 수 있는 기능도 지원
• bucket_count(), load_factor(), max_bucket_count() 등 함수를 통해 컨테이너 내부에서 사용되는 설정 값을 알 수 있다.
• rehash() 함수를 통해 재해싱 수행도 가능하다.
• 이 컨테이너들은 체이닝 기법을 사용해 구현되어있어 key, value 쌍들을 서로 다른 bucket에 저장하고 있다.
  • 검색 연산 시 key가 같은지 비교해야하므로 key는 등호 연산이 정의 되어 있어야한다. 또는 템플렛 매개변수로 비교자 지정 가능

#include <boost/functional/hash.hpp>

strcut Car
{
	...
};

struct CarHasher
{
	std::size_t operator()(const Car& car) const
    {
    	std::size_t seed = 0;
        boost::hash_combine(seed, car.model);
        boost::hash_combine(seed, car.brand);
        return seed;
	}
};

struct CarComparator
{
	bool operator()(const Car& car1, const Car& car2) const
    {
    	return (car1.model == car2.model) && (car1.brand == car2.brand);
	}
};

std::unordered_set<Car, CarHaser, CarComparator> carSet;
std::unordered_map<Car, std::string, CarHasher, CarComparator> carDescriptionMap;

• Boost 라이브러리에서 제공하는 hash_combine() 함수를 사용해 해시 함수를 쉽게 구성할 수 있다.
• unordered_set, map 객체 생성 시 CarHaser 구초제는 () 연산자를 재정의한 함수로, 템플릿 매개 변수로 사용된다.
• CarComparator 구조체는 비교자의 역할을 한다 마찬가지로 템플릿 매개변수로 사용된다.
• 위와 같은 방식을 사용하면 서로 다른 타입의 해시 함수와 비교자를 사용하는 여러 객체를 만들 수 있다.
• MD5, SHA-1, HSA-256 같은 복잡한 암호화 함수도 해시 함수로 사용이 가능하다.
  • 해시값을 원본 데이터를 알아내는 역해싱이 매우 어려워 보안 시스템에서 널리 사용되고 있다.

블룸 필터 (bloom filter)

• cuckoo hashing과 마찬가지로 여러 개의 hash function 사용
• 두개 hash function은 충분한 정확도 X -> 3개 이상 사용
• Bloom Filter는 실제 값을 저장 X, 특정 값이 있는지 Bool Type Array 사용
  • 해시 값에 대응되는 위치의 Bit를 1로 설정
• Look-up의 경우 모든 해시 함수 값 계산 후 이에 대응되는 위치의 bit가 1인지 검사 후 모든 비트가 1이면 true 반환, 1이 아닌게 하나라도 있으면 false 반환(해당 원소 없음)
• Bloom Filter는 해시 테이블에 비해 공간 효율이 매우 높지만 부정확한 결과를 얻을 수 있다.
  • False Negative 없는 것은 보장하지만 False Positive는 나올 수 있다.
  • 특정 비트가 다수 원소에 의해 1로 설정될 수 있기 때문이다. 즉, 특정 값과 연관된 모든 비트가 이전 삽입된 다른 원소로 인해 모두 1로 설정되어 있을 가능성이 있다는 것이다. 원소 개수가 많아질 수록 False Positive 발생 가능성은 증가한다.

0 0 0 0 0 0 0

• h1(x) = x % 7
• h2(x) = (x / 7) % 7
• h3(x) = (x / 11) % 7
• Hash(x) = {h1(x), h2(x), h3(x)}

Hash(100) = {2, 0, 2} 100 삽입
1 0 1 0 0 0 0
Hash(54) = {5, 0, 4} 54 삽입
1 0 1 0 1 1 0
Hash(82) = {5, 4, 0} 82 삽입
1 0 1 0 1 1 0
Hash(5) = {5, 0, 0} 5 검색
1 0 1 0 1 1 0 뭐지 ? 5가 없는데 1이 나오네 ? False Positive
Hash(50) = {1, 0, 4} 50 검색
1 0 1 0 1 1 0 중간에 0이 있으므로 False 절대 없음

#include <iostream>
#include <vector>

class bloom_filter
{
	std::vector<bool> data;
    int nBits;
    
    int hash(int num, int key)
    {
    	switch (num)
        {
        	case 0: return key % nBits;
            case 1: return (key / 7) % nBits;
            case 2: return (key / 11) % nBits;
         }
         
         return 0;
	}
    
public:
	bloom_filter(int n) : nBits(n)
    {
    	data = std::vector<bool>(nBits, false);
	}
    
    void lookup(int key)
    {
    	// 모든 비트가 1로 설정되었는지만 검사하면 된다.
        
    	bool result = data[hash(0, key)] & data[hash(1, key)] & data[hash(2, key)];
        
        if (result)
        {
        	std::cout << " mady be there " << std::endl;
		}
        else
        {
        	std::cout << " Never there " << std::endl;
        }
	}
    
    void insert(int key)
    {
    	data[hash(0, key)] = true;
        data[hash(1, key)] = true;
        data[hash(2, key)] = true;
    }
};

int main()
{
	bloom_filter bf(7);
    bf.insert(100);
    bf.insert(54);
    bf.insert(82);
    
    bf.lookup(5);
    bf.lookup(50);
}

• 위 예시에서는 7비트만 사용했지만, 필터 크기를 좀 더 크게 설정하고 해시 함수 보완 시 훨씬 더 나은 성능을 얻을 수 있다.
• Bloom filter는 데이터 양이 너무 많이 해시테이블조차 사용하기 버겁고, Flase Positive가 있어도 괜찮은 경우 사용한다.