해시법

---

• 해시법은 검색과 더불어 데이터의 추가와 삭제도 효율적으로 수행할 수 있는 방법이다.
• 정렬된 배열에 새로운 값을 추가하려면, 먼저 삽입할 위치를 찾은 후 위치 이후의 값들을 한칸씩 밀고 삽입해야한다.
  
• 배열의 키 값을 요솟수로 나눈 나머지를 해시 값이라고 하며, 이 해시 값은 데이터에 접근할 때 사용한다.
• 해시 값이 인덱스가 되도록 원래의 키 값을 저장한 배열을 해시 테이블이라고 한다.
• 키 값으로 해시 값을 만드는 과정을 해시 함수라고 한다.
• 해시 테이블의 각 요소를 버킷이라고 한다.

충돌

• 새로운 값을 추가한다면 해당 해시 값 인덱스에 값을 넣어 주면 된다.
• 하지만 해당 자리에 이미 값이 존재하는 경우가 있다. 이를 충돌이라고 한다.
• 충돌이 발생하지 않으려고 해시 테이블을 크게 하면 메모리를 쓸데없이 많이 차지하게 된다. 따라서 시간과 공간의 절충이 중요하다.

충돌에 대한 대처

1. 체인법

• 같은 해시 값을 갖는 요소를 연결 리스트로 관리한다

2. 오픈 주소법

• 충돌이 발생했을 때 재해시를 수행하여 비어 있는 버킷을 찾아내는 방법으로, 닫힌 해시법이라고 한다.