해싱 빠른 액세스를 허용하는 방식으로 데이터를 효율적으로 저장하고 검색하는 기본 데이터 구조입니다. 여기에는 해시 테이블의 특정 인덱스에 데이터를 매핑하는 작업이 포함됩니다. 해시 함수 키를 기반으로 정보를 빠르게 검색할 수 있습니다. 이 방법은 데이터베이스에서 일반적으로 사용됩니다. 씨 아프게 하는 시스템과 다양한 프로그래밍 애플리케이션을 통해 검색 작업을 최적화합니다.
데이터 구조 - 해싱
내용의 테이블
작동 방식:
- 해시 함수: 해시 함수에 데이터 항목을 제공합니다.
- 해시 코드: 해시 함수는 데이터를 처리하고 고유한 해시 코드를 제공합니다.
- 해시 테이블: 그런 다음 해시 코드는 해시 테이블 내의 특정 위치를 가리킵니다.
해시 함수
그만큼 해시 함수 을 취하는 함수이다 열쇠 그리고 반환 색인 로 해시 테이블 . 해시 함수의 목표는 해시 테이블 전체에 키를 균등하게 분배하여 충돌을 최소화하는 것입니다(두 키가 동일한 인덱스에 매핑되는 경우).
일반적인 해시 함수는 다음과 같습니다.
- 분할 방법: 키 % 해시 테이블 크기
- 곱셈 방법: (키 * 상수) % 해시 테이블 크기
- 범용 해싱: 충돌을 최소화하도록 설계된 해시 함수 제품군
해시 충돌이란 무엇입니까?
해시 충돌은 두 개의 서로 다른 키가 해시 테이블의 동일한 인덱스에 매핑될 때 발생합니다. 이는 좋은 해시 함수를 사용해도 발생할 수 있으며, 특히 해시 테이블이 가득 차거나 키가 유사한 경우 더욱 그렇습니다.
해시 충돌의 원인:
- 불량한 해시 함수: 해시 테이블 전체에 키를 균등하게 분배하지 않는 해시 함수는 더 많은 충돌을 일으킬 수 있습니다.
- 높은 부하율: 로드 계수(해시 테이블 크기에 대한 키 비율)가 높으면 충돌 가능성이 높아집니다.
- 유사한 키: 값이나 구조가 유사한 키는 충돌할 가능성이 더 높습니다.
충돌 해결 기술
충돌 해결 기술에는 두 가지 유형이 있습니다.
- 공개 주소 지정:
- 선형 프로빙: 빈 슬롯을 순차적으로 검색
- 2차 프로빙: 2차 함수를 사용하여 빈 슬롯 검색
- 폐쇄 주소:
- 연결: 각 인덱스의 연결된 목록 또는 이진 검색 트리에 충돌 키를 저장합니다.
- 뻐꾸기 해싱: 여러 해시 함수를 사용하여 키 배포
해싱의 응용
해시 테이블은 다음을 포함하여 다양한 애플리케이션에 사용됩니다.
- 데이터베이스: 고유 키를 기반으로 데이터 저장 및 검색
- 캐싱: 빠른 검색을 위해 자주 액세스하는 데이터 저장
- 기호 테이블: 프로그래밍 언어의 값에 식별자 매핑
- 네트워크 라우팅: 데이터 패킷에 대한 최적의 경로 결정
해싱이란 무엇입니까?
해싱에 대한 쉬운 문제
- 배열이 다른 배열의 하위 집합인지 확인
- 두 연결리스트의 합집합과 교차점
- 배열 A[]와 숫자 x가 주어지면 A[]에서 합이 x인 쌍을 확인합니다.
- 배열에서 동일한 요소의 두 발생 사이의 최대 거리
- 같은 라인의 최대 포인트 계산
- 배열에서 가장 빈번한 요소
- 1에서 n-1 사이에서 유일하게 반복되는 요소 찾기
- 주어진 두 세트가 서로소인지 확인하는 방법은 무엇입니까?
- 두 세트의 겹치지 않는 합
- 두 배열이 같은지 확인하십시오.
- 범위에서 누락된 요소 찾기
- 고유 요소가 있는 하위 집합의 최소 수
- 두 배열에 공통 요소가 존재하지 않도록 최소 요소 수를 제거합니다.
- 쌍의 요소가 다른 행에 있도록 주어진 합계로 쌍을 찾습니다.
- 주어진 합계로 쌍 계산
- 합계가 주어진 값 x와 동일한 4개의 정렬된 배열에서 4배를 계산합니다.
- 빈도별로 요소 정렬
- a % b = k가 되는 배열에서 모든 쌍 (a, b)를 찾습니다.
- 동일한 문자 세트로 단어 그룹화
- 배열의 k번째 고유(또는 반복되지 않는) 요소입니다.
해싱에 대한 중간 문제
- 주어진 티켓 목록에서 여행 일정 찾기
- 모든 직원 아래의 직원 수 찾기
- 합을 k로 나눌 수 있는 가장 긴 부분 배열
- 합이 0인 가장 큰 부분배열 찾기
- 가장 긴 증가하는 연속 부분 수열
- 크기가 k인 모든 창에서 고유 요소 수 계산
- 주어진 합계로 하위 배열 찾기 | 세트 2(음수 처리)
- Java에서 별도의 연결을 사용하여 자체 해시 테이블 구현
- C++에서 개방형 주소 지정 선형 프로빙을 사용하여 자체 해시 테이블 구현
- 순열이 허용되는 회문을 형성하기 위한 최소 삽입
- 배열의 두 하위 집합의 가능한 최대 차이
- 간단한 해시 함수를 사용하여 정렬
- k개의 고유 숫자를 갖는 가장 작은 부분 배열
해싱의 어려운 문제
- 임의 포인터를 사용하여 이진 트리 복제
- 0과 1의 수가 동일한 가장 큰 부분 배열
- 주어진 값으로 합산되는 모든 고유한 삼중항
- 회문 하위 문자열 쿼리
- 배열 요소의 주파수에 대한 범위 쿼리
- 범위의 모든 요소가 배열에 존재하도록 추가할 요소
- Cuckoo Hashing – 최악의 경우 O(1) 조회!
- 원본 배열과 동일한 총 개별 요소를 갖는 하위 배열 개수 계산
- 동일한 순서를 유지하는 주어진 두 배열의 최대 배열
- 주어진 배열에 대한 모든 고유 하위 배열 합계의 합계를 찾습니다.
- 레카망 수열
- 가장 긴 엄격한 바이토닉 부분 수열의 길이
- 모든 중복 하위 트리 찾기
- 모서리가 1인 이진 행렬에 직사각형이 있는지 확인
빠른 링크 :
- 해싱에 대한 '연습 문제'
- 해싱 기술 기반 인터뷰 질문 상위 20개
- 해싱의 '동영상'
권장사항:
- 데이터 구조와 알고리즘 배우기 | DSA 튜토리얼