CS/자료구조

체이닝 방식을 이용한 해시 충돌 처리를 구현해보자! 체이닝 방식은 해시 테이블에서 충돌이 발생할 경우 충돌된 키를 연결 리스트 형태로 처리하는 방법이다. 충돌이 발생하면 동일한 해시 버킷에 속한 항목들을 연결 리스트로 연결하여 저장한다. 해시를 저장할 버킷을 링크드 리스트로 선언한다. 링크드 리스트에 키값 멤버를 가진 노드를 저장할 것이다. private static final int DEFAULT_BUCKET_SIZE = 1024; private List[] buckets; private int size; private int bucketSize; public MyLinkedHashTable() { this.buckets = new List[DEFAULT_BUCKET_SIZE]; this.bucketS..

Hash 해시는 key, value 쌍으로 이루어진 데이터 구조이다. key는 구현된 hashFunction을 통해 계산된 해시 값(인덱스)으로 bukets에 저장된다. int myhashFunction(K key) { int hash = 0; for (Character ch : key.toString().toCharArray()) { hash += (int)ch; } return hash % this.bucketSize; } hashFunction은 키를 인수로 받는 키를 구현된 로직으로 계산하여 일정 길이의 해시 값을 반환한다. 이러한 해시 값을 인덱스로 사용하여 값을 저장하고 검색한다. 데이터 접근 시 hashFunction으로 키를 계산하여 데이터에 접근하기 때문에 O(1)의 시간 복잡도를 가진다..