알고리즘

[알고리즘] 해싱(자료구조 기말고사 공부 정리)

2022. 5. 30. 18:38
목차
  1. 해싱
  2. 해시 테이블
  3. 해시 함수
  4. 해싱의 문제점
  5. => 오버플로우 해결 방법

해싱

; 해시 함수에 의하여 계산된 키 값의 주소로 직접 접근하는 것

- 해싱 = 'key to address transformation', 즉 특정 규칙에 따라 주어진 키 값을 주소로 변환하여 해시 테이블이라는 기억공간에 키의 레코드를 저장

- 해시 함수를 이용하여 필요한 레코드의 주소를 산출함으로서 검색작업을 수행

 

해시 테이블

; 해시 함수에 의해 산출된 주소에 각 레코드를 기억시킨 테이블

- 버킷들로 구성되어 있으며, 각각의 버킷은 슬롯으로 구성

 

해시 함수

; 입력된 키 값을 해시 테이블의 주소로 변환시켜주는 함수

- 중간 제곱함수 ; 키 값을 제곱한 후 그 수의 중간에 정해진 자리 수만큼을 취해서 해시 테이블의 버킷주소로 만듬

- 나누기 함수 ; 키 값을 해시 테이블의 크기로 나누어서 그 나머지를 버킷 주소로 변환

- Folding 함수 ; 키 값을 버킷 주소 크기만큼의 부분으로 분할한 후, 분할된 것을 더하거나 연산하여 그 결과 주소의 크기를 벗어나는 수는 버리고 택하여 버킷의 주소로 만드는 방법

- 기수 변환법 ; 주어진 키 값을 다른 진법의 수로 판단하고, 이를 진법 변환을 통하여 버킷의 주소를 계산

- 숫자 변환법 ; 모든 키 값들을 임의 기수 숫자로 바꾼 후 모든 자리 수에 대한 테이블을 만들고, 각 자리 수에 대한 숫자별 빈도를 파악하여 특정 숫자로 편중되지 않고 어느 정도 균등한 분포를 갖는 자리수를 주소로 사용

 

해싱의 문제점

; 해싱을 하는 경우 서로 다른 두개 이상의 키 값들이 해시 함수에 의해 동일한 주소로 변환되는 경우, 충돌 발생

-> 출돌이 발생하는 경우 버킷이 여러 슬롯으로 구성되어 있다면 다른 슬롯에 저장

-> 모든 슬롯이 채워지면 오버플로우 발생

=> 오버플로우 해결 방법

- 개방 주소법 ; 한 레코드의 키로부터 관련된 일련의 버킷 주소 생성 -> 생성된 버킷주소에서 충돌이 발생하면 생성된 버킷의 주소로부터 비어있는 버킷이 발견될 때까지 찾음

- 폐쇄 주소법(=체인법) ; 충돌이 발생하는 동의어 별로 연결리스트로 저장되는 방법, 가장 많이 사용

 

저작자표시 (새창열림)

'알고리즘' 카테고리의 다른 글

[알고리즘] 다익스트라  (0) 2022.06.06
[알고리즘] DP(Dynamic Programming)  (0) 2022.06.06
[알고리즘] 선형 리스트(Stack, Queue, Deque)  (0) 2022.06.06
[알고리즘] 해시  (0) 2022.06.06
[알고리즘] 탐색  (0) 2022.05.29
[알고리즘] 그래프  (0) 2022.05.22
[알고리즘] 연결 리스트  (0) 2022.05.21
[알고리즘] 배열과 연결리스트  (0) 2022.05.21
  1. 해싱
  2. 해시 테이블
  3. 해시 함수
  4. 해싱의 문제점
  5. => 오버플로우 해결 방법
'알고리즘' 카테고리의 다른 글
  • [알고리즘] 선형 리스트(Stack, Queue, Deque)
  • [알고리즘] 해시
  • [알고리즘] 탐색
  • [알고리즘] 그래프
피터s
피터s
1년차 프론트엔드 개발자입니다 😣 아직 열심히 배우는 중이에요! 리액트를 하고있어요 :) - gueit214@naver.com - https://github.com/gueit214
피터s
피터의 성장기록
피터s
전체
오늘
어제
  • 분류 전체보기 (200)
    • 코딩 테스트 (25)
      • 프로그래머스 (16)
      • LeetCode (8)
      • 백준 (1)
    • 개발 독서 일지 (1)
    • 기업 분석 (4)
    • 개발 일지 (19)
      • 최신기술 도전기 (1)
      • 에러 처리 (5)
      • 개발 일지 (12)
    • 개발 일상 (36)
      • 개발 회고 (22)
      • 개발 이야기 (12)
      • 개발 서적 (1)
    • 취업 관련 지식 (11)
    • 알고리즘 (17)
    • WebProgramming (84)
      • WebProgramming (8)
      • HTML (5)
      • CSS (8)
      • JS (21)
      • React (40)

블로그 메뉴

  • About
  • 2022년 개발 성장기
  • 앞으로의 계획
  • github
  • 일상 blog

공지사항

인기 글

태그

  • 누적합
  • BFS
  • lv3
  • 해커톤
  • Retry
  • 개발 일상
  • Union-find
  • 반복문
  • Kakao Tech Internship
  • KAKAO BLIND
  • dfs
  • 1일 1커밋 후기
  • 스터디 후기
  • 개발 회고
  • 함수
  • 개발 is life
  • 카카오
  • 구름
  • 카카오 채용연계형 인턴십
  • 구름톤
  • 1년 회고
  • LV2

최근 댓글

최근 글

hELLO · Designed By 정상우.
피터s
[알고리즘] 해싱(자료구조 기말고사 공부 정리)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.