다음 과정을 사용하여 Hash Tables에 대해 스스로 공부하고 있습니다. http://algs4.cs.princeton.edu/34hash/
연습 부분에서 다음을 찾았습니다.
암호 검사기. 명령 줄에서 문자열을 읽고 표준 입력에서 단어 사전을 읽고 "좋은"암호인지 확인하는 프로그램을 작성합니다. 여기서 "good"은 (i) 길이가 8 자 이상, (ii) 사전에있는 단어가 아님, (iii) 사전에있는 단어가 아니라 뒤에 숫자 0-9가 오는 것을 의미한다고 가정합니다 (예 : hello5), (iv)는 숫자로 구분 된 두 단어가 아닙니다 (예 : hello2world).
Hash Table (HashMap)을 사용하는 방법에 대해 혼란스러워합니다. 더 쉬운 연습을 가정 해 보겠습니다. 단어가 사전에 있는지 확인하기 만하면되며 해시 테이블을 사용하여이 작업을 수행해야합니다. 내 생각에는 단어를 키로 사용하여 사전에있는 모든 단어를 추가해야하며 주어진 단어가 사전에 있는지 확인하려면 "get"메소드를 사용합니다. 발견 된 단어는 좋은 암호가 아닙니다. 그러나:
1) 주어진 키와 관련하여 입력해야하는 값은 무엇입니까?
2) 두 단어가 같은 위치에 해시되면 어떻게됩니까? 충돌 부분이 Linear Probing 또는 Separate Chaining을 사용하여 해결된다는 것을 알고 있으므로 get을 사용할 때 데이터 구조에서 처리됩니까?
나는 당신이 어떤 코드도 작성하는 것을 원하지 않습니다. 나는 이것이 어떻게 작동하는지 이해하려고 노력하고 있습니다.
미리 감사드립니다!
@Edit : 내가 가진 또 다른 아이디어는 hashCode 만 사용하는 것입니다. 사전의 모든 단어가 포함 된 문자열 배열이 있다고 가정합니다. 그런 다음 해시 코드가 동일한 경우 비교해야합니다 (해시가 같음과 일치해야하므로). 내가 잘 이해했다면 값은 중요하지 않습니다.이 경우 단어가 사전에 있는지 확인해야합니다. 그래서 나는 내게 무언가가 반환되었는지 확인해야한다.
1) 주어진 키와 관련하여 입력해야하는 값은 무엇입니까?
Java HashSet
구현 을 살펴보면 내부적으로를 사용하고 HashMap
항목이 키로 매핑에 추가되고 값이 모든 항목이 공유하는 더미 객체임을 알 수 있습니다. 귀하의 사전 키 구조는 더를 HashSet
(A)보다 HashMap
, 당신이 키와 연관 (예를 들어 인기 같은) 특정 값이없는 경우.
2) 두 단어가 같은 위치에 해시되면 어떻게됩니까? 충돌 부분이 Linear Probing 또는 Separate Chaining을 사용하여 해결된다는 것을 알고 있으므로 get을 사용할 때 데이터 구조에서 처리됩니까?
Java HashMap
구현은 별도의 체인을 사용하며 동일한 해시 코드를 가진 모든 항목은 연결 목록 구조에 배치됩니다. HashMap을 사용할 때 충돌 해결에 대해 걱정할 필요가 없습니다 (목표가 해시 공격을 방지하는 것이 아니라면).
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다