Hash와 Hash 충동

[참조]

http://hyeonstorage.tistory.com/265

 

----------------------------------------------------------------------------------------------------------

 

 

1. Hash

- 해시를 보기에 앞서 대표적인 자료구조의 배열과 리스트를 본다.

 - 배열의 경우에는 인덱스를 이용하여 자료의 검색이 한번에 이루어지기 때문에 빠른 검색 속도를 보이는 반면 데이터의 삽입, 삭제 시 많은 데이터가 밀리거나 빈자리를 채우기 위해 이동해야 하기 때문에 많은 시간이 소요된다.

 - 연결 리스트의 경우에는 삽입, 삭제 시 인근 노드들의 참조값만 수정해줌으로써 빠른 처리가 가능하다. 단 처음과 마지막 노드 이외의 위치에서 데이터를 삽입, 삭제할 경우나 데이터를 검색할 경우에는 해당 노드를 찾기 위하여 처음부터 순회검색을 해야 하기 때문에 데이터의 수가 많아질수록 효율이 떨어지는 구조였다.

 - 이러한 한계를 극복하기 위해 제시된 방법이 해쉬이다.

 

1-1) Hash의 개념

 - Hash는 내부적으로 배열을 사용하여 데이터를 저장하기 대문에 빠른 검색 속도를 갖는다.

 - 데이터의 삽입과 삭제 시 기존 데이터를 밀어내거나 채우는 작업이 필요 없도록 특별한 알고리즘을 이용하여 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다.

 - 삽입과 삭제 시 데이터의 이동이 없도록 만들어진 구조이다.

 - Hash가 내부적으로 사용하는 배열을 Hash Table이라고 하며 그 크기에 따라서 성능 차이가 많이 날 수 있다.

 

1-2) Hash Mathod

 - Hash는 Hash Table을 이용하여 데이터를 저장한다. 이때 특별한 알고리즘을 이용하여 데이터의 고유한 숫자값을 만들어 인덱스로 사용하는데 이 알고리즘을 구현한 메소드를 Hash Mathod라고 하며, Hash Mathod에 의해 반환된 데이터 고유의 숫자 값을 Hash Code라고 한다.

 - Hash Table의 동일한 인덱스에 데이터 저장을 시도하는 경우에 문제가 발생한다.( 충돌현상, Collision이라고 하며 이러한 충돌을 최소화 하기 위한 방법으로는 나머지 연산의 값이 최대한 중복되지 않도록 테이블의 크기를 소수(Prime Number)로 만든다.)

 - 충돌방지를 해결하기 위한 방법으로는 "개방주소법"과 "분리연결법 두가지가 있다.

 

1-3) 충돌해결 방법(분리연결법)

 

      - 개방주소법의 경우에는 충돌이 많이 일어날 경우 심각한 성능저하가 발생 할 수 있다.

- 분리연결법은 Hash Table에 연결 리스트에서 사용하는 Node 객체를 저장하는 것이다.

- Hash Table의 셀마다  연결 리스트를 하나씩 저장하도록 하고 충돌이 발생하는 데이터는 연결 리스트의 다음 노드로 계속 추가해 가는 것이다.

- 이후에 데이터를 검색할 때에는 Hash Table의 인덱스를 찾은 후 셀에 연결된 리스트를 순차적으로 탐색하며 착으려는 hashCode와 저장된 HashCode를 비교한는 것이다.

 

 

1-3) 충돌해결 방법(개방주소법)

 - 개방주소법은 배열만을 사용하며, 저장 인덱스가 겹칠경우 해당 인덱스의 옆 인덱스에 저장하는 방식이다. 이때 옆 인덱스와의 데이터 충돌이 또다시 일어나면 다시 옆 인덱스로 저장한다. 따라서 충돌 데이터가 많이 발생하면 성능에 심각한 문제가 발생하는 단점이 있다.

1-4) 해시의 크기

1-5) 해시 자료구조의 종류와 차이