# Open Addressing

nayu1105

해시테이블이란? > 해시테이블은 Key-Value 형태로 저장되는 자료구조로, 평균 O(1)의 시간복잡도를 가진다. 흔히, HashMap이라고 불리기도 한다. key 값을 을 이용해, Hash Table에 저장할 위치를 정한다. 대표적인 Hash Function에는 가 있다. 해시충돌(Hash Collision)이란? >해시 충돌은 어떤 entry를 넣으려고 할때, Hash Function으로 찾은 위치에 이미 다른 entry가 존재하는 경우 발생한다. 즉, 다른 키 값일때, Hash Function을 통해 같은 값을 가지게 되는 경우 해시 출돌이 발생한다. 해시충돌 해결 방법 1 : 체이닝(Chaining) 같은 주소로 해싱 될 때, 연결 리스트(Linked List)로 연결하는 방식 추가 공간 활용 <img src="https://velog.velcdn.com/images/nayu1105/post/b12

kaifa

Java에서 Hashtable은 키(key)와 값(value)을 쌍으로 저장하는 자료구조이다. 각 키는 해시 함수(hash function)를 통해 고유한 해시 값(hash value)으로 변환되고, 이 해시 값은 해당 키-값 쌍이 저장될 배열 인덱스를 결정한다. 이러한 방식으로 Hashtable은 상수 시간(constant time)에 키-값 쌍을 검색할 수 있다. Hashtable은 내부적으로 배열을 사용하여 키-값 쌍을 저장한다. 각 키에 대한 해시 값을 계산하고, 해당 값에 매핑된 배열 인덱스에 값을 저장한다. 배열의 크기는 일반적으로 저장할 수 있는 최대 요소 수에 따라 결정된다. Hashtable의 크기가 배열 크기에 도달하면 자동으로 더 큰 배열을 만들고, 모든 요소를 새 배열에 다시 해싱한다. Hashtable의 검색, 삽입, 삭제는 모두 상수 시간(constant time)에 수행된다. 그러나 배열 크기가 매우 클 경우 **해시 충돌(hash collis

samag

1. 해시 테이블이란? 해시 테이블이란 키를 해시 함수를 이용해 연산함으로써 고정된 길이의 결과값을 얻을 수 있고 이 결과값을 이용하여 키와 값을 매핑할 수 있는 형태의 자료구조이다. 이처럼 해시 함수를 이용해 키와 값을 매핑하는 것을 해싱이라 하며 해싱은 정보를 빠르게 저장하고 검색하기 위해 사용되는 중요한 기법이다. apple -> 10 orange -> 00 banana -> 01 이처럼 key값을 넣었을 때 고정된 길이의 해시된 값을 얻고 해당 값을 이용해 데이터를 저장하고 검색한다. 2. 해시 값이 충돌할 경우 충돌 서로 다른 값의 키를 계산했을 때 같은 결과의 해시값이 나오는 경우를 충돌했다고 표현한다. 그렇다면 충돌이 발생할 확률은 얼마나될

citizenyves

0. Hash Colision 해시함수가 모든 입력에 대해 항상 다른 해시값을 부여할 수 있다면 이상적인 상황이다. 하지만 모든 데이터에 대해 알고 있지 않다면 이렇게 완벽한 해시 함수를 작성하는 것은 불가능하다. 해시 충돌(hash colision)은 키(key)가 들어갈 자리(bucket)이 없는 경우에 발생하는 개념이다. 위와 같이 B와 C라는 키값이 해시함수를 통과하면 4라는 동일한 hash 값을 부여받게 된다. 이것이 해시 충돌이다. 한편, 해시테이블의 가장 중요한 목적은 해시 충돌을 최소화 시키는 해시함수를 만드는데 있다. 해시충돌이 벌어지는 상황을 파이썬 코드로 구현해본다. 해시 충돌로 인해 발생하는 문제를 해결하는데 가장 대표적인 두가지 방법을 알아본다. 먼저, Chainin

haero_kim

Hash 데이터를 다루는 기법 중 하나이다. 우리는 이미 해시라는 단어에 익숙하다. 인스타그램의 '해시태그' 기능 역시 해시 기법을 이용하여 게시물들을 구분하는 것이다. 아래처럼 #맛집 이라고 검색하게 되면, #맛집이라는 해시태그가 달려있는 게시물들이 한 뭉탱이로 묶여서 보여지게 된다. '#맛집' 이라는 데이터로 매핑된 게시물들이다. Hash Function 데이터를 효율적으로 관리하기 위해 어떤 길이의 데이터든 하나로 고정된 길이의 데이터로 매핑하는 함수 매핑 전 원래 데이터를 Key, 매핑 된 후 데이터 값을 Hash Value 혹은 해시코드 라고 한다. → Key-Value 타입으로 매핑되는 과정 자체를 **`Hashi

thms200

Hash Table이란? 해시테이블 출처 : 위키백과 - 해시테이블 > 해시 테이블(hash table) 자료 구조 중 하나로, Key와 Value를 저장한다. Key, Hash Function, Hash, Value로 구성된다. 의 전화번호인 를 저장한다고 하자. 입력된 를 에 적용해서 라는 값을 얻는다. 그러면 는 미리 중 에 저장하게 된다. 이후 Key 값으로 John Smith를 입력하면, Hash Function을 통해 02라는 위치값을 알게되고, 그 위치에 저