알고리즘 자료구조 - 12

11장

1)
해시법(hashing)
 - 데이터를 저장할 위치(인덱스라 한다)를 간단한 연산으로 구하는 알고리즘
 - 검색뿐만 아니라 데이터의 추가, 삭제를 효율적으로 수행하는 알고리즘

 - "배열의 각 요소의 값(데이터)을 배열의 전체요소 개수로 나눈 나머지"를 배열의 요소로 해서 데이터를 표에 정리한 내용을 해시값(hash value, 배열의 인덱스)이라고 하며, 
   해시법은 해시값을 사용하여 데이터 접근을 수행한다

 - 해시함수(hash function)
    : 해시 값을 구하기 위해 나머지를 구하는 연산 혹은 이런 나머지 연산을 다시 응용한 연산을 사용하는 함수
  ** 해시함수로 해시 값(배열의 인덱스)을 구하며, 해시값이 적절하지 못해 해시함수를 약간 변형하여 해시하는 것을 재해시라 한다

 - 해시 테이블(hash table): 해시 값이 인덱스가 되도록 원래의 키 값(데이터 중 정렬 기준이 되는 데이터)을 저장한 배열 
 - 버킷(bucket): 해시 테이블의 각 요소


2)
해시법의 충돌
 - 키 값과 해시 값간의 대응관계는 n:1(왜냐하면 데이터가 훨씬 많아 겹치는 조건이 존재할 수 있다)이며, 이렇게 키값을 기준으로 데이터를 저장할 배열의 버킷이 중복되는 현상을 충돌(collision)이라고 한다
 - 충돌 발생시 대처법
    1) 체인법 : 같은 해시 값을 갖는 데이터를 연결리스트로 관리하는 방법
    2) 오픈 주소법 : 빈 버킷을 찾을 때 까지 해시를 반복(정확히는 해시함수를 약간 변형하여 해시를 반복하는 재해시 수행)


3)
체인법(chaining)
 - 같은 해시 값을 갖는 데이터를 쇠사슬과 같이 연결리스트로 구성하는 방법. 
 - 오픈 해시법(open hashing)이라고도 한다


 - 해시 테이블에 저장하는 데이터는 구조체 형태의 노드 이며, 데이터와 (연결리스트로 구성된) 다음노드에 대한 포인터를 맴버로 가진다
 - 데이터가 없을 경우 해시 테이블과 노드의 포인터는 NULL 값을 가진다

 - 해시 테이블을 관리하는 구조체는 해시 테이블의 크기(배열의 총 요소 수)와 해시 테이블을 가리키는 포인터를 맴버로 가진다
 - 해시 함수의 경우 키 값을 테이블 크기로 나눈 나머지를 반환한다

 - 함수 구성
    hash, setnode, initialize, search, add, remove, clear(노드 메모리 해제 및 해시테이블의 버킷 NULL), terminate(해시테이블 배열 해제)


** 해시함수와 해시 테이블
 - 해시법으로 데이터 추가시 충돌이 발생하지 않는다고 가정하면 검색, 추가, 삭제에 대한 시간복잡도는 O(1)이지만, 메모리는 데이터에 따라 점점 커지게 된다
 - 따라서 시간과 공간의 절충(trade-off, 자원의 효율화)을 해야하는 문제가 발생한다
 - 이를 위해 충돌을 줄이는 것이 좋은데, 해시 테이블의 크기는 소수의 크기를 가지는 것이 좋다
 - 만약 키 값이 정수가 아니고, 실수라면 비트연산(bitwise operation), 문자열이라면 각 문자코트에 곱셈과 덧셈을 하는 방법이 있다


4)
오픈 주소법(open addressing)
 - 같은 해시 값을 갖는 데이터가 있을 경우(충돌 발생 시) 재해시(rehashing)를 수행하여 비어있는 버킷을 찾고 해당 버킷에 저장하는 방법
 - 닫힌 해시법(closed hashing), 선형 탐사법(linear probing)이라고도 한다

 - 해시함수를 사용하여 해시 후, 데이터를 저장 이때 데이터 충돌 발생시 (키값+1)/요소수를 수행 (재해시) 그 이후에도 충돌하면 재해시 반복
 - 해시 테이블에 저장된 데이터 삭제시, 그냥 비우는 게 아닌 삭제 라는 상태를 따로 부여한다. 삭제시 해시함수로 구한 인덱스의 데이터가 삭제 상태를 가리키면 재해시를 반복 수행하여 삭제할 데이터를 찾는다

 - 요소의 구조체는 데이터와 요소의 상태를 맴버로 가지고, 해시테이블을 관리하는 구조체는 테이블크기, 테이블을 가리키는 포인터를 맴버로 가진다
 - 함수
    initialize, search, add, remove(삭제 상태 값으로 저장), clear(진짜 데이터 삭제(empty)), termiate(메모리 해제)