별의 공부 블로그 🧑🏻‍💻

🗒️ 체이닝 (2)

728x90
  1. 2021.05.20 [C++] 체이닝(Chaining)을 이용한 해시 테이블(Hash Table) 구현

    체이닝(Chaining)을 이용한 해시 테이블(Hash Table) 구현 체이닝(Chaining) 해시 테이블에 두 값을 모두 저장할 수 있는 여러 방법 중 하나 해시 테이블의 특정 위치에서 하나의 키 를 저장하는 것이 아니라 하나의 연결 리스트 를 저장함. 새로 삽입된 키에 의해 충돌이 발생하면 리스트의 맨 뒤에 새로운 키를 추가함. 따라서 다수의 원소를 원하는 만큼 저장할 수 있음. 벡터 대신 연결 리스트를 사용하는 이유? 특정 위치의 원소를 빠르게 삭제하기 위함. 코드 #include #include #include #include using uint = unsigned int; class hash_map { std::vector data; public: hash_map(size_t n) { dat..

  2. 2017.06.20 [C] 해싱(Hashing)

    해싱(Hashing) [해싱이란?] - 대부분의 탐색 방법들은 탐색 키를 저장된 키 값과 반복적으로 비교함으로써 탐색하고자 하는 항목에 접근함. - 하지만 해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근함. - 해시 테이블(hash table) : 키 값의 연산에 의해 직접 접근이 가능한 구조 - 해싱(hashing) : 해시 테이블을 이용한 탐색 - 해싱은 일상생활에서의 정리 정돈으로 비유할 수 있음. - 키들의 비교에 의한 탐색 방법은 정렬이 안 되어 있으면 O(n)이고 정렬되어 있으면 O(log₂n). - 이 정도의 시간 복잡도가 허용되는 경우도 있는 반면, 어떤 경우는 더 빠른 탐색 방법이 필요함. - 해싱은 이론적으로는 O(1)의 시간 안..

728x90
📖 Contents 📖

티스토리툴바