hash
-
해시(Hash)와 해시 충돌 해결 방법CS(Computer Science)/Data Structure 2021. 11. 26. 16:08
1. 해시란? 💡 데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 매핑 해시 함수: 데이터를 효율적으로 관리하기 위해 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값을 해시 코드, 해시라고 한다. 해시 테이블: 키와 값을 매핑해둔 데이터 구조이다. 해시 함수로 얻은 해시를 키로 활용하여 index로 사용하고 해당 index에 데이터를 저장하여 효율적인 검색을 위해 사용된다. 1-1. 해시 순서 해당 원소의 해시 함수를 이용하여 해시값을 얻는다. 해시값을 주소로 하는 위치에 원소를 저장한다. 저장 후 검색 시에도 원소의 해시값으로 계산하여 해당 위치로 이동한다. 1-2. 사용 용도 무결성 검사: 파일 다운로드..
-
해시 알고리즘알고리즘/문제풀이 2020. 9. 20. 23:00
이번 시간에는 해시 알고리즘에 대해서 알아본다. 해시 테이블과 해시 테이블에서 충돌이 발생하는 경우 해결방법 2가지를 알아본다. 1. Direct Addressing Table 크기가 U인 테이블 T를 생성하고 key k를 slot key에 저장하는 방식이다. 해당 테이블은 중복되는 키가 없다고 가정한다. 이는 삽입, 삭제, 검색 모두 O(1)이지만, 모든 키를 넣어야 하기 때문에 공간 낭비가 심하다. 예를 들어 모든 학생들에게 한 자리씩 할당해 준 것이다. 2. Hash Table key k를 저장할 때 slot k를 저장하는 것이 아니라 slot h(k)에 저장한다. key k가 slot h(k)로 해시되었다고 하며, h(k)를 key k의 해시값이라고 부른다. 이때 h( )는 해시 함수라고 부른다...