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

해시 테이블 또는 해시 맵이라고도하는 연관 배열은 배열의 인덱스가 정수 대신 문자열 일 수 있다는 점을 제외하고 표준 배열과 유사합니다. 많은 데이터베이스 응용 프로그램 및 많은 양의 데이터를 처리하는 다른 프로그램에서 관련 배열은 효율적인 방식으로 정보를 정렬하고 액세스하는 데 중요한 요소입니다. 연관 배열의 핵심에는 보통 경우와 같이 정수로 색인이 생성 된 표준 배열이 있습니다. 해시 함수라는 특수 알고리즘은 문자열 색인을 정수 색인으로 변환하여 값을 찾습니다. 이것은 일관된 변환이므로 실제 정수 인덱스를 저장할 필요는 없지만 매번 필요에 따라 문자열에서 계산됩니다.

연관 배열을 나타낼 때 사용되는 용어는 일반 배열에 대해 말할 때 사용되는 용어와 약간 다를 수 있습니다. 일반적으로 인덱스 (배열 내부의 요소의 숫자 위치)라고하는 것을 키라고합니다. 키와 관련된 데이터를 값이라고합니다. 이는 연관 배열 내에서 키가 데이터 구조의 표준 배열에있는 요소를 참조하는 색인과 상관되는 값과 연관됨을 의미합니다.

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

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

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

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