일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- Tuist
- UIViewControllerTransitioningDelegate
- 상단 탭바
- List
- Side Menu
- detect url
- development language
- DataBinding
- base64 변환
- url 추적
- ViewBuilder
- oberve url
- url 관찰
- convert base64
- UIPresentationController
- 스크롤 탭
- scrolling tab
- 개발자 면접
- notifychanged
- GeometryReader
- SwiftUI
- DevelopmentRegion
- pod install
- ios
- 기존 앱
- transformation.map
- Swift Package Manager
- Android
- swift
- swift #swift keychain #keychain 사용법
- Today
- Total
버그 잡이
[자료구조] 해시테이블(HashTable)이란 무엇인가? +HashMap 본문
1. HashTable란 도대체 무엇?
해시테이블은 해시함수를 거쳐 만들어진 key와 해시함수를 거치기 전 데이터인 value를 묶어 함께 저장하는 자료구조이다.
(여기서 key값은 value값에 대한 색인, 주소 역할을 한다.)
*용어 정리
*Hash 함수 : 일정 값이 input인풋으로 들어가면 고정된 길이의 값을 output으로 반환해주는 함수
*Hashing : 특정 value가 hash함수를 거쳐 key값을 반환하고 key:value형태로 해쉬 테이블에 저장되는 모든 과정
2. 특징
"리소스 < 속도"
해시 테이블을 만들기 위해서는 key값이라는 것을 기억할 새로운 메모리 공간이 필요하기 때문에 기존 방법보다 리소스가 많이 든다.
하지만 key값으로 바로 value값을 찾을 수 있기 때문에 찾는 속도는 O(1)이다.
#왜 시간 복잡도가 O(1)인가?
예를 들어, "알고" : "마스터" 라는 쌍으로 저장을 한다고 가정해봅시다.
내부적으로 해쉬 테이블은 key값인 "알고" 를 해시함수에 넣어 특정한 정수값을 만듭니다.
이후 이 정수값을 활용하여 data[정수값] = "마스터" 형식으로 배열에 담는 것입니다.
그 결과 이후 "알고" 라는 키워드로 검색하면 똑같이 해시함수가 동작해 정수값을 반환해주고
그 정수값을 index로 해서 값을 바로 찾아올 수 있는 것입니다.
"해시 충돌의 문제"
서로 다른 value에 대해서 해시 함수로 처리한 결과값이 같을 수 있다.
이 경우 같은 공간에 한 개 이상의 value가 들어가려고 하기 때문에 문제가 된다.
*해결 방법
1. chaining : 충돌이 일어나면 기존값과 새로운 값을 연결리스트를 이용해 연결한다.
2. open addressing : 충돌이 일어나면 비어있는 다른 버켓에 저장한다.
3. 코드로 구현하기
연결리스트로 chaining이 적용된 예시입니다.
import java.util.*
fun main(){
val hashTable = HashTable(3)
hashTable.put("알고", "마스")
print(hashTable.get("알고"))
}
class HashTable(val size : Int){
var data = MutableList<LinkedList<Node>>(size){
LinkedList<Node>()
}
class Node(val key: String, var value: String){
}
//해쉬 함수
fun getHashCode(key: String) : Int{
var hashCode = 0
for (c in key.toCharArray()){
hashCode += c.toInt()
}
return hashCode
}
//해쉬코드를 정수값으로 변형(size에 맞게 넣어야 하기 때문)
fun convertToIndex(hashCode: Int): Int{
return hashCode % size-1
}
//링크드리스트에서 해당 key값 찾기
fun searchKey(list : LinkedList<Node>, key: String) : Node? {
if(list == null) null
for(node in list){
if(node.key.equals(key)){
return node
}
}
return null
}
fun put(key: String, value: String){
val hashCode = getHashCode(key)
val index = convertToIndex(hashCode)
var list: LinkedList<Node> = data[index]
//해당 배열 방 링크드리스트에 key와 같은 값이 있는지 확인
val node = searchKey(list, key)
//해당 key값이 없다면 추가, 있다면 변경
if(node == null){
list.addLast(Node(key, value))
} else {
node.value = value
}
}
fun get(key: String) : String{
val hashcode = getHashCode(key)
val index = convertToIndex(hashcode)
val list = data[index]
val node = searchKey(list, key)
return node?.value ?: "not found"
}
}
*참고 : www.youtube.com/watch?v=Vi0hauJemxA
+ 자바에서 HashTable vs HashMap
- HashMap은 보조 해시 함수를 사용해서 해시 충돌이 덜 발생한다.
- HashMap은 동기화를 지원하지 않는다(그래서 동시화를 지원하는 HashTable이 좀 더 느리다고 한다.)
'CS > 자료구조' 카테고리의 다른 글
[자료구조] Heap이란? (0) | 2020.06.22 |
---|---|
Java Collections - List, Set, Map (0) | 2020.06.19 |
[자료구조] 배열과 리스트 +ArrayList, LinkedList (0) | 2020.06.08 |