[YYBASIC0202/얌얌코딩] DAT(Direct Addressing Table) - Hash Table

• 데이터를 찾기 위해서는 해당 데이터의 위치(주소)를 알고 있어야 합니다.
• 이 방법의 시간 복잡도는 O(1)로, 한 번의 접근만으로 데이터 검색을 완료할 수 있습니다.
• 해시 테이블(Hash Table)과 DAT는 이러한 원리를 기반으로 만들어진 자료구조로, 배열의 각 요소를 인덱스를 통해 직접 메모리 주소와 연결하여 빠른 데이터 조회가 가능합니다.

해시 테이블(Hash Table)과 해시 함수(Hash Function)

• 해시 테이블은 데이터를 특정 인덱스로 변환하여 저장하는 자료구조입니다. 이는 입력 값에 해시 함수(Hash Function)를 적용하여 특정 주소(인덱스)를 계산하는 방식을 사용합니다.
• 해시 함수는 입력된 키를 특정 범위 내의 인덱스로 변환합니다. 이 과정에서 서로 다른 키가 같은 인덱스로 변환되는 충돌(Collision)이 발생할 수 있습니다.
• 이러한 충돌을 해결하는 방법 중 하나가 **체이닝(Chaining)**이며, 이는 같은 인덱스에 여러 개의 데이터를 연결 리스트 형태로 저장하는 방식입니다.
• 해시 테이블을 이용하면 정렬이 가능하며, 기존 정렬 알고리즘보다 코드를 단순화하고 처리 속도를 향상시킬 수 있습니다.
• 하지만 고정된 크기의 배열을 사용하므로 메모리 낭비가 발생할 수 있습니다. 데이터의 양에 비해 테이블 크기가 크다면 불필요한 메모리 소비가 발생할 수 있습니다.

DAT(Direct Addressing Table)

• **DAT(직접 주소 지정 테이블, Direct Address Table)**은 특정 키(Key)를 사용하여 원하는 값에 직접 접근하는 방식입니다.예를 들어, 주소를 알고 있는 집에 바로 방문하는 것과 같은 원리입니다.
• 배열을 활용하여 특정 위치에 빠르게 접근할 수 있는 자료구조로, 배열의 인덱스를 키 값과 직접 연결하여 빠른 검색이 가능합니다.
  • 예를 들어, 배열의 인덱스를 아스키 코드 값으로 활용하면 알파벳 문자의 개수를 효율적으로 카운트하는 코드를 작성할 수 있습니다.

LV03 DAT(HashTable), 패턴 찾기