99클럽 코테 스터디 9일차 TIL + 오늘의 학습 키워드 문자열 해시

- 오늘의 학습 키워드 문자열 해시
- 공부한 내용 본인의 언어로 정리하기

해시맵: 키랑 값을 같이 저장하는 자료구조, 해시 함수를 이용해서 키를 배역의 인덱스로 변환

ⓐ내부적으로 배열을 사용해서 데이터를 저장

ⓑ해시 함수로 키를 배열 인덱스로 매핑

ⓒ-1체이닝으로 충돌을 처리한다. 

 

수도코드

class MyHashMap:
    initialize:
        Create array of linked lists (buckets)
        Set size of array (ex: 1000)
    
    hash_function(key):
        return key % size
    
    put(key, value):
        index = hash_function(key)
        Find bucket at index
        If key exists in bucket:
            Update value
        Else:
            Add new (key, value) pair to bucket
    
    get(key):
        index = hash_function(key)
        Find bucket at index
        If key exists in bucket:
            Return value
        Else:
            Return -1
    
    remove(key):
        index = hash_function(key)
        Find bucket at index
        If key exists in bucket:
            Remove (key, value) pair

 

- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

해시 함수 key% SIZE 를 사용하지 못했음
  - 어떻게 해결했는지

gpt 랑 다시 공부함
  - 무엇을 새롭게 알았는지

key % size를 사용하는 이유

키 값이 얼마든지 0~ size-1 사이의 값으로 매핑된다.

모든 키가 배열의 유효한 인덱스 범위내로 변환된다.

  - 내일 학습할 것은 무엇인지 

 

---

ⓒ-2 충돌시 선형탐색을 이용함

오픈 어드레싱: 모든 키랑 값의 쌍을 해시맵의 배열 내부에 직접 저장한다. 충돌이 발생하면 다른 빈 슬롯을 찾아서 저장한다.

 

선형 탐색방

충돌 발생시 다음 슬롯을 확인하며 빈 슬롯을 찾는다.

탐색, 삽입, 삭제 시 모두 같은 방식으로 슬롯을 찾는다.

삭제된 슬롯은 다르게 표시하여 검색 과정이 중단되지 않게 한다.

 

클래스 MyHashMap:
    // 해시맵의 크기와 저장 공간
    크기 = 초기 크기 (예: 1000)
    키배열 = 새 배열[크기]
    값배열 = 새 배열[크기] 
    상태배열 = 새 배열[크기]  // 0: 비어있음, 1: 사용중, 2: 삭제됨
    
    생성자 MyHashMap():
        모든 상태 배열 초기화 (0: 비어있음)
    
    함수 해시함수(키):
        return 키 % 크기
    
    함수 put(키, 값):
        인덱스 = 해시함수(키)
        
        // 비어있거나 삭제된 슬롯을 찾을 때까지 선형 탐색
        시작인덱스 = 인덱스
        while 상태배열[인덱스] == 1 AND 키배열[인덱스] != 키:
            인덱스 = (인덱스 + 1) % 크기
            if 인덱스 == 시작인덱스:
                return  // 테이블이 가득 참
        
        // 키와 값 저장
        키배열[인덱스] = 키
        값배열[인덱스] = 값
        상태배열[인덱스] = 1
    
    함수 get(키):
        인덱스 = 해시함수(키)
        
        // 키를 찾을 때까지 선형 탐색
        시작인덱스 = 인덱스
        while 상태배열[인덱스] != 0:  // 비어있지 않은 동안
            if 상태배열[인덱스] == 1 AND 키배열[인덱스] == 키:
                return 값배열[인덱스]
            인덱스 = (인덱스 + 1) % 크기
            if 인덱스 == 시작인덱스:
                break  // 전체 테이블 탐색 완료
        
        return -1  // 키를 찾지 못함
    
    함수 remove(키):
        인덱스 = 해시함수(키)
        
        // 키를 찾을 때까지 선형 탐색
        시작인덱스 = 인덱스
        while 상태배열[인덱스] != 0:  // 비어있지 않은 동안
            if 상태배열[인덱스] == 1 AND 키배열[인덱스] == 키:
                상태배열[인덱스] = 2  // 삭제됨으로 표시
                return
            인덱스 = (인덱스 + 1) % 크기
            if 인덱스 == 시작인덱스:
                return  // 전체 테이블 탐색 완료

선형 탐색을 쓸때?

로드팩터(적재율이)가 낮을때

테이블이 많이 차있지 않은 상태, 충돌이 발생해도 보통 바로 옆칸이 비어있어 빈자리를 찾기 쉽다.

메모리 지역성이 중요할때: 배열안에 모든 데이터가 연속으로 저장되어있어 ,메모리에서 데이터를 가져올때 요청한 위치근처의 데이터를 함께 가져오기 때문에 편리하다.

작은 키와 값을 저장할때 체이닝은 각 항목마다 포인터를 추가로 저장해야하지만  선형탐색은 추가포인터가 필요없어서 메모리를 절약할수있따.

해시충돌이 적은상황에서 서로 키가 같은 해시값(인덱스를) 가지는 경우 해시충돌이 일어난다.

충돌이 적으면 선형탐색에서 다음칸으로 이동하는일이 거의 없어 바로 원하는 위치에 접근할수 있는 선형탐색이 유리함