99클럽 코테 스터디 2일차 TIL + Hash

학습 키워드

- Hash

 

공부한 내용

• ArrayList는 내부 인덱스를 이용하여 검색이 한번에 이루어지기 때문에 빠른 검색 속도를 보장하는 반면 데이터의 추가/삭제시 많은 데이터가 밀리거나 당겨지기 때문에 많은 시간이 소요된다. LinkedList는 추가/삭제시 인근 노드들의 참조값만 수정해 줌으로써 빠른 처리가 가능하지만 데이터를 검색할 경우 해당 노드를 찾기 위해 처음부터 순회 검색을 해야하기 때문에 데이터의 수가 많아질수록 효율이 떨어지는 구조이다.

→ 이러한 한계를 극복하기 위해서 제시된 방법이 Hash이다.

Hash

• 해시(Hash)는 입력 데이터를 고정된 데이터로 변환된 값을 말한다. 다른 말로 해시 값(Hash Value), 해시 코드, 체크섬 이라고도 한다.
• 이러한 해시는 ‘해시 함수’에 의해서 얻게 된다. 즉, 데이터의 Key 값이 해시 함수를 통해서 변환된 간단한 정수이다.
• 정수로 변환된 해시는 배열의 인덱스, 위치, 데이터 값을 저장하거나 검색할 때 활용된다.
• 해시는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다.
• 특정 데이터가 저장되는 인덱스를 그 데이터만의 고유한 위치로 정하여서 데이터 추가/삭제시 데이터의 이동이 없도록 만들어진 구조이다.

⇒ HashMethod 를 써서 HashTable에 저장하는 것을 Hashing이라고 한다.

자료 구조의 특징

• 키(KEY)에 데이터(Value)를 매핑할 수 있는 데이터 구조
• 해시 함수를 통해 키의 데이터를 배열에 저장할 수 있는 주소(인덱스 번호)를 계산
• 키를 통해서 저장된 데이터를 빠르게 찾고, 저장 및 탐색 속도가 획기적으로 빨라짐

용어

해시 함수(Hash Function)

• 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수이다.
• 해시 함수는 입력받은 데이터를 해시 값으로 출력시키는 알고리즘을 말한다.

해시 테이블(Hash Table)

• 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조이다.
• 해시 테이블은 키와 값을 함께 저장해 둔 데이터 구조이다. 이는 데이터가 행과 열로 구성된 표에 저장되는 것과 유사하다. 테이블에 데이터를 저장할 때 위치는 무작위로 지정되어 작성된다.
• → 중간에 여유 공간이 발생할 수 있다.

• 버킷(bucket) : 하나의 주소를 갖는 파일의 한 구역, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수
• 슬롯(slot) : 한 개의 레코드를 저장할 수 있는 공간, 한 버킷 안에 여러 개의 슬롯이 있음

해싱(Hashing)

• 해싱은 해시 함수에서 해시를 출력하고, 해시 테이블에 저장하는 과정까지의 행위를 말한다.

해시 자료구조의 장단점과 주요 용도

장점

• 데이터 저장 / 읽기 속도가 빠르다. (검색 속도가 빠르다.)
• 해시는 키에 대한 데이터가 있는지 확인이 쉽다.

단점

• 일반적으로 저장공간이 많이 필요하다.
• 여러 키에 해당하는 주소(인덱스)가 동일한 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다.

주요 용도

• 검색이 많이 필요한 경우
• 저장, 삭제, 읽기가 빈번한 경우
• 캐쉬 구현하는 경우

• JAVA 에서는 주로 HashMap 클래스를 사용한다.

 

회고

발생한 문제

- 코딩 문제를 풀다가 Hash에 대한 공부가 부족했음을 깨닫게 되었다. 그래서 이번 기회에 Hash를 공부해보았다.

 

해결 방법

- Hash에 대한 개념부터 차근차근 공부해보았다. 사실 아직 어렵게 느껴지지만 그래도 좋은 경험이 되었다. 

 

알게된 내용

- Hash에 대한 공부를 하게 되었다. 다른 자료구조보다 더 어렵게 느껴졌다. 그래도 조금씩 공부해 나가야겠다. 

 

추후 학습할 내용

- 또 다른 자료구조 공부를 할 생각이다. 아직 공부할 부분이 많아서 무엇을 먼서 공부할지 고민이다. 

 

 

참고 자료

- https://jroomstudio.tistory.com/10

- https://kang-james.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%95%B4%EC%8B%9CHASH-%EC%95%8C%EC%95%84%EB%B3%B4%EA%B8%B0