Java의 접기 기술에 대한 사용방법(예제)

1. 소개

이 예제에서는 요소에 대한 지속적인 액세스를 제공하는 다양한 데이터 구조에서 사용되는 해싱 기술을 고려합니다.

소위 폴딩 기술에 대해 자세히 논의 하고 미드 스퀘어 및 비닝 기술에 대해 간략하게 소개합니다.

2. 개요

객체 저장을위한 데이터 구조를 선택할 때 고려해야 할 사항 중 하나는 객체에 빠르게 액세스해야하는지 여부입니다.

Java 유틸리티 패키지는 객체 저장을위한 많은 데이터 구조를 제공합니다. 데이터 구조에 대한 자세한 내용 은 여러 가지에 대한 사용방법(예제)가 포함 된 Java 컬렉션 컴파일 페이지를 참조하십시오.

아시다시피, 이러한 데이터 구조 중 일부는 포함 된 요소의 수에 관계 없이 일정한 시간에 요소를 검색 할 수 있습니다.

아마도 가장 간단한 것은 배열 일 것입니다. 실제로 우리는 인덱스로 배열의 요소에 액세스합니다. 액세스 시간은 당연히 어레이의 크기에 의존하지 않습니다. 실제로 많은 데이터 구조에서 배열을 많이 사용합니다.

문제는 배열 인덱스가 숫자 여야하지만 우리는 종종 이러한 데이터 구조를 객체로 조작하는 것을 선호한다는 것입니다.

이 문제를 해결하기 위해 많은 데이터 구조에서 배열 인덱스 역할을 할 수있는 숫자 값을 개체에 할당하려고합니다. 이 값을 해시 값 또는 단순히 해시 라고합니다 .

3. 해싱

해싱 은 개체를 숫자 값으로 변환하는 것입니다 . 이러한 변환을 수행하는 함수를해시 함수라고합니다.

단순함을 위해 문자열을 배열 인덱스, 즉 유한 N을 가진 [0, N] 범위의 정수로 변환하는 해시 함수를 고려해 보겠습니다 .

당연히 해시 함수는 다양한 문자열에 적용됩니다 . 따라서 "전역"속성이 중요해집니다.

불행히도 해시 함수가 항상 다른 문자열을 다른 숫자로 변환하는 것은 불가능합니다 .

우리는 문자열의 수가 [0, N] 범위의 정수 수보다 훨씬 크다는 사실을 쉽게 확신 할 수 있습니다 . 따라서 해시 함수가 동일한 값을 생성하는 동일하지 않은 문자열 쌍이있는 것은 불가피합니다. 이 현상을 충돌 이라고 합니다.

해시 함수이면의 엔지니어링 세부 사항에 대해 자세히 살펴 보지는 않겠지 만, 좋은 해시 함수가 숫자로 정의 된 문자열을 균일하게 매핑해야한다는 것은 분명합니다.

또 다른 분명한 요구 사항은 좋은 해시 함수가 빠르다는 것입니다. 해시 값을 계산하는 데 시간이 너무 오래 걸리면 요소에 빠르게 액세스 할 수 없습니다.

이 예제에서는 매핑 을 빠르게 유지하면서 균일하게 만드는 기술 중 하나를 고려 합니다.

4. 접는 기술

우리의 목표는 문자열을 배열 인덱스로 변환하는 함수를 찾는 것입니다. 아이디어를 설명하기 위해이 배열이 105 ^개의 요소를 수용 할 수있는 용량을 원한다고 가정하고 문자열 Java 언어 를 예로 사용하겠습니다 .

4.1. 기술

문자열의 문자를 숫자로 변환하여 시작하겠습니다. ASCII는이 작업에 적합한 후보입니다.

이제 우리는 방금 얻은 숫자를 일정한 크기의 그룹으로 정렬합니다. 일반적으로 배열의 크기 인 10 ^5를 기준으로 그룹 크기 값을 선택합니다 . 문자를 변환 한 숫자는 일반성을 잃지 않고 2 ~ 3 자리 숫자를 포함하므로 그룹 크기를 2로 설정할 수 있습니다.

다음 단계는 각 그룹의 숫자를 문자열 인 것처럼 연결하고 합계를 찾는 것입니다.

이제 우리는 마지막 단계를해야합니다. 숫자 348933 이 크기 10 ⁵ 배열의 인덱스 역할을 할 수 있는지 확인해 보겠습니다 . 당연히 최대 허용 값인 99999를 초과합니다 . 최종 결과를 찾기 위해 모듈로 연산자를 적용하면이 문제를 쉽게 해결할 수 있습니다.

348933 % 10000 = 48933

4.2. 마지막 비고

알고리즘에는 시간이 많이 걸리는 작업이 포함되어 있지 않으므로 매우 빠릅니다. 입력 문자열의 모든 문자가 최종 결과에 기여합니다. 이 사실은 충돌을 줄이는 데 확실히 도움이되지만 완전히 피하는 것은 아닙니다.

예를 들어 접기를 건너 뛰고 모듈로 연산자를 ASCII로 변환 된 입력 문자열에 직접 적용하려는 경우 (오버플로 문제 무시)

749711897321089711010311797103101 % 100000 = 3101

그런 다음 해시 함수는 입력 문자열과 동일한 마지막 두 문자 인 ge , p age , lar ge 등 을 가진 모든 문자열에 대해 동일한 값을 생성합니다 .

알고리즘의 설명을 통해 충돌로부터 자유롭지 않다는 것을 쉽게 알 수 있습니다. 예를 들어 알고리즘은 Java 언어 및 vaJa 언어 문자열에 대해 동일한 해시 값을 생성합니다 .

5. 기타 기술

접는 기술은 매우 일반적이지만 유일한 방법은 아닙니다. 때로는 비닝 또는 중간 제곱 기술도 유용 할 수 있습니다.

우리는 문자열이 아니라 숫자를 사용하여 그들의 아이디어를 설명합니다 (이미 문자열을 숫자로 변환했다고 가정합니다). 장점과 단점에 대해서는 논의하지 않겠지 만 알고리즘을보고 의견을 낼 수 있습니다.

5.1. 비닝 기법

100 개의 정수가 있고 해시 함수가이를 10 개 요소의 배열로 매핑하려고한다고 가정합니다. 그런 다음 처음 10 개의 정수가 첫 번째 빈에서 끝나고 두 번째 10 개의 정수가 두 번째 빈에서 끝나는 방식으로 100 개의 정수를 10 개의 그룹으로 배열 할 수 있습니다.

5.2. 미드 스퀘어 기법

이 알고리즘은 John von Neumann이 제안했으며 주어진 숫자에서 시작하는 의사 난수를 생성 할 수 있습니다.

구체적인 예를 들어 설명하겠습니다. 4 자리 숫자 1111 이 있다고 가정 합니다. 알고리즘에 따라 제곱하여 1234321 을 얻습니다 . 이제 중간에서 4 자리 숫자를 추출합니다 (예 : 2343) . 알고리즘을 통해 결과에 만족할 때까지이 프로세스를 반복 할 수 있습니다.

6. 결론

이 사용방법(예제)에서는 몇 가지 해싱 기술을 고려했습니다. 우리는 접는 기술을 자세히 설명하고 비닝과 미드 스퀘어를 달성 할 수있는 방법에 대한 플래시 설명을 제공했습니다.

항상 그렇듯이 GitHub 저장소 에서 해당 코드 스 니펫을 찾을 수 있습니다 .

참고

• https://docs.spring.io/spring-framework/docs/current/reference/html
• https://www.baeldung.com/folding-hashing-technique