연관 배열이란 무엇입니까?

해시 테이블 또는 해시 맵이라고도하는 연관 배열은 배열의 인덱스가 정수 대신 문자열 일 수있는 것을 제외하고 표준 배열과 유사합니다. 많은 데이터베이스 애플리케이션 및 다량의 데이터를 다루는 다른 프로그램에서 연관 배열은 효율적인 방식으로 정보를 정렬하고 액세스하는 데 도움이되는 중요한 요소입니다. 연관 배열의 핵심에는 일반적으로 그렇듯이 정수로 인덱싱 된 표준 배열이 있습니다. 해시 함수라는 특수 알고리즘은 문자열 인덱스를 정수 인덱스로 변환하여 값을 찾습니다. 이것은 일관된 변환이므로 실제 정수 지수는 절대 저장 될 필요가 없지만 매번 필요에 따라 문자열에서 계산됩니다.

연관 배열을 참조 할 때 사용되는 용어는 일반 어레이에 대해 이야기 할 때 사용되는 것과 약간 다를 수 있습니다. 일반적으로 인덱스라고 불리는 것은 배열 내부의 요소의 수치 위치 인 색인이라고합니다.열쇠. 키와 관련된 데이터를 값이라고합니다. 이는 연관 배열 내에서 키가 값과 관련되어 있으며, 이는 데이터 구조의 표준 배열에서 요소를 참조하는 인덱스와 관련이 있음을 의미합니다.

.

모든 연관 배열의 핵심은 해시 함수입니다. 이것은 키를 기반으로 값의 숫자 색인을 결정하는 데 사용되는 알고리즘입니다. 몇 가지 유형의 해시 함수가 있으며, 일부는 정수 인 키에서 작동하도록 설계되었으며 일부는 문자열 인 키에서 작동하도록 설계되었습니다. 정수 키의 경우, 인기있는 방법은 키 값을 배열의 크기로 나누고 나머지 부서를 사용하여 고유 한 인덱스 값을 얻는 것입니다.

.

해시 함수는 문자열 인 키에 대해 훨씬 더 복잡 할 수 있습니다. 일부 방법에는 문자열에서 각 문자의 숫자 값을 추가 한 다음 숫자로 나누는 것이 포함됩니다.또는 문자열의 처음 몇 문자 만 사용하여 고유 한 숫자를 얻습니다. 문자열에서 숫자를 도출하는 방법에는 여러 가지가 있습니다.

연관 배열에서 많은 양의 키 값 쌍을 다룰 때 발생할 수있는 한 가지 문제를 충돌이라고합니다. 충돌은 키에서 파생 된 정수 색인이 다른 키의 정수 인덱스와 동일 할 때 발생합니다. 이 두 키는 값 배열에서 동일한 인덱스를 효과적으로 가리 킵니다. 충돌에 대한 다양한 솔루션이 있습니다. 주로 대부분의 실제 응용 분야에서 발생할 가능성이 높기 때문입니다.

충돌을위한 하나의 솔루션은 각 값 지수를 실제로 링크 된 목록으로 만드는 것입니다. 따라서 둘 이상의 키가 해당 인덱스 위치로 해결되면 위치가 둘 이상의 값을 유지할 수 있습니다. 이를 체인이라고하며 충돌을 처리하는 간단한 방법이지만 정보를 검색하는 데 걸리는 시간이 느려질 수 있습니다. 충돌을 다루는 또 다른 방법을 선형 프로브라고합니다.충돌이 발생하면 미사용 인덱스가 발견 될 때까지 값 배열을 통해 이동하여 선형 프로브가 작동합니다. 이 솔루션은 데이터를 연관 배열에 골고루 분산시키는 데 도움이 될 수 있지만 값을 찾는 데 필요한 시간을 늘릴 수도 있습니다.

.