CS/자료구조2 [자료구조] 해시 함수(Hash Function) / 해시 테이블(Hash Table) 해시 함수(Hash Function)란 ? 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이 때, 매핑 전 원래 데이터의 값을 키, 매핑 후 데이터의 값을 해시값, 매핑하는 과정을 해싱이라고 합니다. 해시 함수는 해시값의 개수보다 많은 키값을 해시값으로 변환하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌이 발생하게 됩니다. 이러한 해시 충돌 발생 가능성이 있음에도 불구하고 해시 테이블을 사용하는 이유는 적은 리소스로 많은 데이터를 효율적으로 관리하기 위함입니다. 해시 함수는 항상 동일한 해시값을 리턴하고, 해당 색인만 알면 해시테이블의 크기와 상관없이 데이터에 빠르게 접근할 수 있으며 색인은 상수 시간으로 작동하기 .. 2022. 9. 8. [자료구조][C++] Map Map이란 ? Key와 Value로 이루어진 자료구조로 Key와 Value가 하나의 쌍으로 연결되어 Key를 통해 Value에 접근할 수 있도록 만들어졌습니다. Map의 특징 Key의 중복을 허용하지 않아야 한다. 순서가 유지되지 않는다. Value의 중복은 허용된다. Map의 종류 HashMap 중복을 허용하지 않는다. 순서를 보장하지 않는다. TreeMap 이진검색트리의 형태로 Key와 Value의 쌍으로 이루어진 데이터를 저장한다. 순서를 보장하며 저장하므로 빠른 검색이 가능하다. 저장할 때 정렬을 하기 때문에 시간이 오래 걸린다. LinkedHashMap 데이터 입력한 순서대로 쌓아 저장한다. 배열, 리스트처럼 인덱스 접근에 용이하다. Map 기본 형태 map m; Map 사용방법 1. Map 선.. 2022. 9. 6. 이전 1 다음
