해싱

해싱이 무엇인가?

검색 키가 주어진 데이터 레코드를 빠르게 찾는 데 사용되는 기술

어떻게?

1. 해시 함수를 사용하여 입력(또는 중요)을 고유한 해시 코드로 변환
2. 해시 코드는 해당 키와 연관된 데이터가 해시 테이블에 저장되는 인덱스를 결정
3. 해시 코드가 데이터 위치를 직접 가리키기 때문에 빠른 데이터 검색이 가능

비밀번호 password123 → 해시 함수를 이용해서 해시 코드로 변환

→ 5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8

→ 비밀번호 (password123:5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8)

내가 password123을 사용하고 싶으면5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8 이 해시코드를 통해 찾을 수 있다.

그러면 key - value로 정해져있다는 건데.

먄약 value가 같은 경우는 어떻게 처리하는가?

즉 충돌이 발생하는 경우는 없는가?

서로 다른 키가 동일한 인덱스에 해시될 수 있으므로(충돌) 충돌을 처리하기 위한 전략이 사용

• 체이닝 (연결리스트 사용)ex) 1:A) → (2:B) → (3:C)
  • 해시 테이블의 크기를 초과하는 데이터도 저장 가능
  • 동적 크기 확장 가능 (연결 리스트 사용)
  • 데이터 삭제가 용이 (연결 리스트에서 해당 노드만 제거하면 됨)
  ❌ 단점
  • 연결 리스트가 길어지면 탐색 속도가 느려짐
  • 메모리 오버헤드 발생
    • 연결리스트의 포인트 공간이 늘어나야 하기때문에
  ex) 자바의 해시 맵

  import java.util.Hashtable;
  import java.util.LinkedList;
  
  public class HashTable {
      private LinkedList<Node>[] table;
  
      public HashTable(int size) {
          table = new LinkedList[size]; // 배열 크기 지정
          for (int i = 0; i < size; i++) {
              table[i] = new LinkedList<>(); // 각 버킷에 LinkedList 초기화
          }
      }
  
      private int hash(int key) {
          return key % table.length;
      }
  
      public void insert(int key, String value) {
          int index = hash(key);
          Node newNode = new Node(key,value);
          table[index].add(newNode);
      }
  
      public String search(int key) {
          int index = hash(key);
          for (Node node : table[index]) {
              if(node.key == key) {
                  return node.value;
              }
          }
          return null;
      }
      private class Node {
          private int key;
          private String value;
  
          public Node(int key, String value) {
              this.key = key;
              this.value = value;
          }
      } 
  }
  

• 예제 코드
• ✅ 장점
• : 해시 테이블의 각 슬롯에는 동일한 인덱스로 해시되는 여러 키-값 쌍이 저장된 연결 리스트(또는 다른 데이터 구조)가 포함되어 있습니다.
• 오픈 어드레싱해시 테이블은 배열로 만들어진다.빈 슬롯을 찾는 방법
  • 선형 탐색 (Linear Probing)
    • 새로운 인덱스 = (현재 인덱스 + 1) % 테이블 크기
    • 🚨 문제: 연속된 충돌이 생기면 성능이 저하될 수 있음(클러스터링 문제 발생)
  • 이차 탐색 (Quadratic Probing)
    • 새로운 인덱스 = (현재 인덱스 + n^2) % 테이블 크기
    • 예: +1^2, +2^2, +3^2 ... 형태로 이동
    • 🎯 장점: 클러스터링 문제 감소
  • 이중 해싱 (Double Hashing)
    • 새로운 인덱스 = (현재 인덱스 + (재해시 값)) % 테이블 크기
    • 🎯 장점: 더 균등하게 분산됨
• 용량이 커지면 재 해싱과정이 필요하다.
• : 이 접근 방식은 해시 테이블 내부를 조사하여 충돌한 키에 대한 대체 위치를 찾고, 결국 모든 키가 고유한 슬롯을 찾도록 보장합니다.

해싱 함수 설계 방법

• 나눗셈 방식
  • hash(key) = key % p
  • 해시 값을 계산할 때 키 값에 대해 특정 수로 나눈 나머지를 사용하여 인덱스를 계산
  • 가장 간단하다.
• public class DivisionMethodHash { public static int hash(int key, int tableSize) { return key % tableSize; // 나머지 연산 } public static void main(String[] args) { int tableSize = 10; // 해시 테이블 크기 System.out.println(hash(35, tableSize)); // 출력: 5 } }
• 중간 제곱법

public class MidSquareMethodHash {
    public static int hash(int key) {
        int square = key * key;  // 제곱
        String squareStr = Integer.toString(square);
        int middleIndex = squareStr.length() / 2;  // 중간 인덱스
        // 중간 부분을 추출하여 해시 값으로 사용
        return Integer.parseInt(squareStr.substring(middleIndex - 1, middleIndex + 1));
    }

    public static void main(String[] args) {
        System.out.println(hash(35));  // 출력: 12 (35^2 = 1225, 중간은 12)
    }
}

• hash(key) = middle_digits(key^2)
• 키 값에 특정 상수를 곱한 뒤, 그 결과의 일부를 사용하여 해시 값을 계산합니다. 이 방식은 분포를 고르게 만들기 위해 상수를 적절히 선택하는 것이 중요
• 폴딩 방식

public class FoldingMethodHash {
    public static int hash(int key) {
        String keyStr = Integer.toString(key);
        int hashValue = 0;
        int n = keyStr.length();
        // 문자열을 두 부분으로 나누어 합산
        for (int i = 0; i < n / 2; i++) {
            hashValue += keyStr.charAt(i) + keyStr.charAt(n - i - 1);
        }
        return hashValue;
    }

    public static void main(String[] args) {
        System.out.println(hash(35));  // 출력: 106 ('3' + '5' = 106)
    }
}

• hash(key) = (key1 + key2 + ... + keyn) % p
• 키 값을 여러 부분으로 나누고, 그들을 합쳐서 해시 값을 생성합니다. 예를 들어, 문자열을 두 부분으로 나누고, 각각의 해시값을 더하여 새로운 해시값을 생성하는 방식
• 곱셈 방식

public class MultiplicationMethodHash {
    public static int hash(int key) {
        double A = (Math.sqrt(5) - 1) / 2;  // (sqrt(5) - 1) / 2
        double result = key * A;
        return (int)(result * 1000) % 1000;  // 일정 범위로 조정
    }

    public static void main(String[] args) {
        System.out.println(hash(35));  // 출력: 247
    }
}

• hash(key) = floor(n * A) % p
• 매우 빠르고 고르게 분포된 해시 값을 생성하는 알고리즘으로, 많은 해시 맵 구현에서 사용

ex) 자바에서 해시를 만드는 코드

(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)

참고 블로그)

https://www.fynd.academy/blog/hashing-in-data-structure

feat. chat gpt