Hash란?
ArrayList는 빠른 검색 속도를 보장하지만 데이터의 추가/삭제시 데이터를 밀고 당기기 때문에 많은 시간이 소요됩니다.
LinkedList는 데이터의 추가/삭제시 참조값 수정을 통해 빠른처리가 가능하지만, 데이터를 검색할 경우 처음부터 노드를 찾기 때문에 효율이 떨어집니다.
이런 단점을 보완하기 위해 만들어진 방법이 Hash입니다.
Hash 는 내부적으로 HashTable이라는 배열을 이용하여 저장하기 때문에 검색속도가 빠릅니다.
데이터와 연관된 해시값을 만들어 이를 인덱스로 활용하기 때문에 데이터 추가/삭제시 밀고 당기는 작업이 필요없습니다.
해시테이블
해시테이블은 Key와 Value로 이루어져 있습니다.
Key를 이용해 Hash Function(해시함수) 을 거쳐 Hash Value를 나타냅니다.
해시함수는 어떤 입력값이 들어와도 항상 고정된 길이 의 해시값을 출력합니다.
해시함수의 특징
해시함수에 글자를 넣었을 경우 의미를 유추할 수 없는 글자가 출력됩니다.
한 글자만 달라졌지만 전혀 다른값이 출력됩니다.
단방향 암호화 방식을 사용하기 때문에 출력값으로 입력값을 예측할 수 없습니다.
해시의 사용 예
데이터베이스에 비밀번호를 저장할 때 해시함수로 암호화해서 저장
이 경우에는 해커가 데이터베이스에서 비밀번호를 탈취해도 유저의 암호를 알 수 없어 해당 유저로 접속할 수 없습니다.
복제문서인지 판별
모든 단어를 비교하는 것 보다 해시값을 비교하는 작업이 훨씬 빠르기 때문에 복제문서 판별을 빠른 속도로 할 수 있습니다.
해시를 사용하는 이유
데이터 탐색 : O(1)
데이터 삽입 : O(1)
데이터 삭제 : O(1)
배열로 저장한 경우 : O(N)
리스트로 저장한 경우 : O(N)
해시의 단점
Hash값들을 저장할 공간이 필요하기 때문에 저장공간이 많이 필요합니다.
여러 Key에 해당하는 Hash가 동일한 경우 해시 충돌(Hash Collision)이 발생합니다.
해시 충돌 해결법
해시 충돌(Hash Collision)을 해결하는 방법은 크게 두가지 방법이 있습니다.
- Separate Chaining(Chaining) 기법
값이 들어가 있는 공간에 또 값이 들어올 경우 충돌이 발생합니다.
이 때 새로 들어오면서 충돌된 Value를 기존값의 뒤에 체인처럼 이어 붙여줍니다. 여러 정보가 함께 존재하도록 설정한 것 입니다.
장점
1. 한정된 저장 공간을 효율적으로 사용할 수 있습니다.
2. 해시 함수에 대한 의존성이 상대적으로 적습니다.
3. 그때그때 이어 붙이기 때문에 메모리 공간을 미리 잡아 놓을 필요가 없습니다.
단점
1. 한 hash에만 자료가 계속 몰리면 검색 효율이 떨어집니다.(최악의 경우 O(n)까지 가능)
2. 외부 저장공간을 사용합니다.
- Open Addressiong(개방주소법) 기법
데이터의 Hash가 변경되지 않는 chaining기법과는 다르게 비어있는 Hash를 찾아 데이터를 저장하는 기법입니다. 그래서 1개의 Hash와 1개의 Value가 매칭되어 있는 형태를 유지합니다.
장점
1. 추가 저장공간이 필요없습니다.
단점
1. 해시함수의 성능이 전체 해시테이블의 성능을 좌지우지합니다.
2. 데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해야 합니다.
