Hash

Hash란?

• 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것
• 해시 함수를 구현하여 데이터 값을 해시 값으로 매핑함
• 배열이나 링크드 리스트의 단점을 극복하기 위해 제시된 방법
• 해시값은 데이터의 key 값이 해시 함수를 통해 변환된 간단한 정수임
• 정수로 변환된 해시는 배열의 인덱스, 위치, 데이터 값을 저장하거나 검색할 때 활용

해시의 특징

• 내부적으로 배열을 사용하여 데이터를 저장하기에 검색 속도 빠름
• 데이터의 삽입/삭제 시 해시 알고리즘을 이용하여 데이터와 연관된 고유한 숫자를 만들어 인덱스로 사용
• 해시가 내부적으로 사용하는 배열을 Hash Table이라고 하며, 크기에 따라서 성능 차이가 남

해시 메서드(Hash Method)

• 입력받은 데이터를 해시 값으로 출력시키는 알고리즘을 말함
• 함수는 목적에 맞게 다양하게 설계되고 자료구조, 캐시, 검색, 에러 검출, 암호 등으로 유용하게 사용됨
• 가장 쉬운 방법으로는 나머지 연산자를 이용하는 방법이 있음

해시 테이블

• 키와 값을 함께 저장해둔 데이터 구조
• 데이터가 행과 열로 구성된 표에 저장되는 것과 유사함
• 테이블에 데이터를 저장할 때 위치는 무작위로 지정되어 작성됨
• 데이터가 많아지면 다른 데이터가 같은 해시값으로 변환되어 충돌나는 collision 현상이 발생함
• 그럼에도 불구하고 해시테이블 사용하는 이유
  • 적은 자원으로 많은 데이터를 효율적으로 관리하기 위해
  • 하드디스크나 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능해지기 때문
  • 언제나 동일한 해시값을 리턴
  • index를 알면 빠른 데이터 검색이 가능함
  • 해시 테이블의 시간 복잡도는 O(1)

해싱

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

충돌 문제 해결법

1. 체이닝

• 연결리스트로 노드를 계속 추가해나가는 방식
• 제한 없이 계속 연결 가능
• 메모리 문제 생길 수 있음

2. Open Addressing

• 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용
• 해당 키 갑셍 저장되어 있으면 다음 주소에 저장

3. 선형 탐사

• 정해진 고정 폭으로 옮겨 해시값의 중복을 피함

4. 제곱 탐사

• 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함

해시 버킷 동적 확장

• 해시 버킷의 크기가 충분히 크다면 해시 충돌 빈도를 낮출 수 있음
• 하지만 메모리는 한정되어 있으므로 무작정 큰 공간을 할당해줄 수 없음
• load factor가 일정 수준 이상이라면(0.7 ~ 0.8) 해시 버킷의 크기를 활장하는 동적 확장 방식을 사용
  • load factor : 할당된 키의 개수 / 해시 버킷의 크기
• 해시 버킷이 동적 확장될 때 리해싱 과정을 거치게 됨
  • 리해싱 : 기존 저장되어 있는 값들을 다시 해싱하여 새로운 키를 부여하는 것을 말함

주요 용도

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

해시 구현 코드

// 기본적인 해시 테이블 구현
public class Hash {

    // Hash table
    public Slot[] hashTable; // 배열 형태로 선언

    // Hash 객체를 생성할 때 table 사이즈 지정
    public Hash(Integer size) {
        this.hashTable = new Slot[size];
    }

    // Slot에는 value를 가짐
    public class Slot {

        String value;

        Slot(String value) {
            this.value = value;
        }
    }

    //Hash function
    public int hashFunction(String key) {
        return (int)(key.charAt(0)) % this.hashTable.length; // 나머지
    }
	
    // 입력 받은 key를 해시 함수로 인덱스화 하고, 해당 인덱스에 value 저장
   public boolean saveData(String key, String value) {

		// key는 해시 함수를 거쳐서 해시 값(해시, 해시 주소)을 반환 -> 여기선 배열의 index와 동일
        Integer address = this.hashFunction(key);

		if(this.hashTable[address] != null) { // 해당 주소에 이미 데이터가 있을 경우
        	this.hashTable[address].value = value;
        } else {
        	this.hashTable[address] = new Slot(value);
        }
        
        return true;
    }

	// key에 해당하는 값을 반환
    public String getData(String key) {

		// key는 해시 함수를 거쳐서 해시 값(해시, 해시 주소)을 반환
        Integer address = this.hashFunction(key);

        if(this.hashTable[address] != null) {
            return this.hashTable[address].value;
        } else {
            return null;
        }
   }

예상 면접 질문

1. 해시 충돌이 발생했을때의 시간 복잡도는 어떻게 될지 설명해주세요.

• 해시 충돌이 발생하면 버켓 안의 모든 값들을 조사해야 하므로 O(n)의 접근 시간을 가집니다.

2. Hash Map과 Hash Table의 차이점에 대해서 설명해주세요

• Hash Map과 Hash Table은 둘 다 키-값 쌍의 데이터를 저장하고 검색하는 자료구조
• 하지만 두 자료구조 사이에는 동기화 지원 여부와 null값 허용 여부 차이가 있음
• Hash Table은 동기화되어 있고 null 값을 허용하지 않음
• Hash Map은 동기화되어 있지 않고, null 값을 허용함

참고

https://kang-james.tistory.com/136
https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Data%20Structure/Hash.md