logo

TechCodeview

해시 테이블 데이터 구조

해시 테이블이란 무엇입니까?

해시 테이블은 키-값 쌍을 빠르게 삽입, 조회 및 제거하는 데 사용되는 데이터 구조로 정의됩니다. 그것은에서 작동합니다 해싱 개념 , 여기서 각 키는 해시 함수에 의해 배열의 고유한 인덱스로 변환됩니다. 인덱스는 일치하는 값의 저장 위치 역할을 합니다. 간단히 말해서 키를 값과 매핑합니다.

부하율이란 무엇입니까?

해시 테이블의 로드 팩터는 테이블 크기와 관련하여 얼마나 많은 요소가 유지되는지에 따라 결정됩니다. 로드율이 높으면 테이블이 복잡해지고 검색 시간이 길어지며 충돌이 발생할 수 있습니다. 좋은 해시 함수와 적절한 테이블 크기 조정을 사용하면 이상적인 로드 비율을 유지할 수 있습니다.



해시 함수란 무엇입니까?

키를 배열 인덱스로 변환하는 함수를 해시 함수라고 합니다. 충돌을 줄이고 빠른 조회 속도를 보장하려면 적절한 해시 기능을 통해 키가 배열 전체에 고르게 분산되어야 합니다.

  • 정수 우주 가정: 키는 정수 유니버스 가정에 따라 특정 범위 내의 정수로 가정됩니다. 이를 통해 나누기 또는 곱셈 해싱과 같은 기본 해싱 작업을 사용할 수 있습니다.
  • 부문별 해싱: 이 간단한 해싱 기술은 키의 남은 값을 배열 크기로 나눈 후 인덱스로 사용합니다. 배열 크기가 소수이고 키 간격이 균등하면 성능이 좋습니다.
  • 곱셈에 의한 해싱: 이 간단한 해싱 작업은 결과의 소수 부분을 취하기 전에 키에 0과 1 사이의 상수를 곱합니다. 그 후, 인덱스는 분수 구성 요소에 배열 크기를 곱하여 결정됩니다. 또한 키가 균등하게 분산되어 있어야 효과적으로 작동합니다.

해시 함수 선택 :

적절한 해시 함수를 선택하는 것은 키의 속성과 해시 테이블의 의도된 기능을 기반으로 합니다. 키를 균등하게 분배하고 충돌을 줄이는 기능을 사용하는 것이 중요합니다.

해시 함수가 선택되는 기준은 다음과 같습니다.



  • 충돌 횟수를 최소로 유지하려면 좋은 해시 함수가 해시 테이블 전체에 키를 균일한 방식으로 배포해야 합니다. 이는 모든 키 쌍에 대해 두 키가 테이블의 동일한 위치로 해싱될 가능성이 다소 일정해야 함을 의미합니다.
  • 빠른 해싱과 키 검색을 활성화하려면 해시 함수가 계산적으로 효율적이어야 합니다.
  • 해시 값에서 키를 추론하는 것은 어려울 것입니다. 결과적으로 해시 값을 사용하여 키를 추측하려는 시도는 성공할 가능성이 적습니다.
  • 해시 함수는 해시되는 데이터가 변경됨에 따라 조정될 수 있을 만큼 유연해야 합니다. 예를 들어, 해시되는 키의 크기나 형식이 변경되더라도 해시 함수는 계속해서 제대로 작동해야 합니다.

충돌 해결 기술 :

두 개 이상의 키가 동일한 배열 인덱스를 가리킬 때 충돌이 발생합니다. 체인화, 개방형 주소 지정 및 이중 해싱은 충돌을 해결하는 몇 가지 기술입니다.

  • 공개 주소 지정 : 충돌은 테이블에서 다음 빈 공간을 찾아 처리됩니다. 첫 번째 슬롯이 이미 사용된 경우 하나가 비어 있을 때까지 다음 슬롯에 해시 함수가 적용됩니다. 이중 해싱, 선형 프로빙, ​​2차 프로빙 등 이 접근 방식을 사용하는 다양한 방법이 있습니다.
  • 별도의 체인 : 별도의 연결에는 해시 테이블의 각 슬롯에 해시되는 개체의 연결된 목록이 있습니다. 두 개의 키가 동일한 슬롯에 해시되면 연결 목록에 포함됩니다. 이 방법은 사용이 매우 간단하며 여러 충돌을 관리할 수 있습니다.
  • 로빈후드 해싱: 체인 길이를 줄이기 위해 Robin Hood 해싱의 충돌은 키를 꺼서 해결됩니다. 알고리즘은 새 키가 이미 점유된 슬롯에 해시되는 경우 두 키의 슬롯과 점유된 슬롯 사이의 거리를 비교합니다. 기존 키가 이상적인 슬롯에 가까울 경우 새 키로 교체됩니다. 이렇게 하면 기존 키가 이상적인 슬롯에 더 가까워집니다. 이 방법은 충돌과 평균 체인 길이를 줄이는 경향이 있습니다.

동적 크기 조정:

이 기능을 사용하면 테이블에 포함된 요소 수의 변경에 따라 해시 테이블을 확장하거나 축소할 수 있습니다. 이는 이상적이고 빠른 조회 시간인 로드 팩터를 촉진합니다.

해시 테이블 구현

Python, Java, C++ 및 Ruby는 해시 테이블을 지원하는 프로그래밍 언어 중 일부에 불과합니다. 표준 라이브러리에 자주 포함되는 것 외에도 사용자 정의 데이터 구조로 사용할 수 있습니다.



예 – String geeksforgeeks의 문자 수를 계산합니다.

이 예에서는 문자열 개수를 저장하기 위해 해싱 기술을 사용합니다.

C++ 
#include  using namespace std; int main() {  //initialize a string  string s='geeksforgeeks';    // Using an array to store the count of each alphabet   // by mapping the character to an index value  int arr[26]={0};    //Storing the count  for(int i=0;i
자바 
public class CharacterCount {  public static void main(String[] args) {  // Initialize a string  String s = 'geeksforgeeks';  // Using an array to store the count of each alphabet  // by mapping the character to an index value  int[] arr = new int[26];  // Storing the count  for (int i = 0; i < s.length(); i++) {  arr[s.charAt(i) - 'a']++;  }  // Search the count of the character  char ch = 'e';  // Get count  System.out.println('The count of ' + ch + ' is ' + arr[ch - 'a']);  } }>
파이썬 
# Initialize a string s = 'geeksforgeeks' # Using a list to store the count of each alphabet # by mapping the character to an index value arr = [0] * 26 # Storing the count for i in range(len(s)): arr[ord(s[i]) - ord('a')] += 1 # Search the count of the character ch = 'e' # Get count print('The count of ', ch, ' is ', arr[ord(ch) - ord('a')])>
씨# 
using System; class Program {  static void Main(string[] args) {  //initialize a string  string s = 'geeksforgeeks';  // Using an array to store the count of each alphabet   // by mapping the character to an index value  int[] arr = new int[26];  //Storing the count  for (int i = 0; i < s.Length; i++) {  arr[s[i] - 'a']++;  }  //Search the count of the character  char ch = 'e';  // get count  Console.WriteLine('The count of ' + ch + ' is ' + arr[ch - 'a']);  } }>
자바스크립트 
// Initialize a string const s = 'geeksforgeeks'; // Using an array to store the count of each alphabet // by mapping the character to an index value const arr = Array(26).fill(0); // Storing the count for (let i = 0; i < s.length; i++) {  arr[s.charCodeAt(i) - 'a'.charCodeAt(0)]++; } // Search the count of the character const ch = 'e'; // Get count console.log(`The count of ${ch} is ${arr[ch.charCodeAt(0) - 'a'.charCodeAt(0)]}`);>


산출:

The count of e is 4>

해시 테이블의 복잡성 분석:

조회, 삽입, 삭제 작업의 경우 해시 테이블의 평균 시간 복잡도는 O(1)입니다. 그러나 이러한 작업은 최악의 경우 O(n) 시간이 필요할 수 있습니다. 여기서 n은 테이블의 요소 수입니다.

해시 테이블의 응용:

  • 해시 테이블은 대량의 데이터를 인덱싱하고 검색하는 데 자주 사용됩니다. 검색 엔진은 해시 테이블을 사용하여 색인을 생성한 웹 페이지를 저장할 수 있습니다.
  • 데이터는 일반적으로 해시 테이블을 통해 메모리에 캐시되므로 자주 사용하는 정보에 빠르게 액세스할 수 있습니다.
  • 해시 함수는 디지털 서명을 생성하고, 데이터의 유효성을 검사하고, 데이터 무결성을 보장하기 위해 암호화에 자주 사용됩니다.
  • 해시 테이블을 사용하여 데이터베이스 인덱스를 구현하면 키 값을 기반으로 데이터에 빠르게 액세스할 수 있습니다.