들어가기에 앞서
참고한 자료를 바탕으로 비전문가가 정리한 글이므로 오류가 있을 수 있습니다.
오류에 대한 지적 사항은 언제든지 환영합니다. 부디 댓글로 알려주시길 바랍니다. 감사합니다.
HashTable?
HashTable은 key와 value형태로 데이터를 저장하는 자료구조입니다. Hashtable은 key를 해시 함수에 입력하여 해시 코드를 생성하고, 이 해시 코드를 배열의 인덱스로 사용하여 value를 저장하거나 검색합니다.
Hashtable은 효율적인 검색을 위한 자료구조이지만, 몇 가지 단점도 있습니다. 예를 들어, 해시 함수가 서로 다른 key에 대해 같은 해시 코드를 생성할 수 있습니다. 이를 해시 충돌(Hash Collision)이라고 하며, 이를 해결하기 위한 방법들이 있지만, 추가적인 시간과 공간이 필요합니다. 또한, Hashtable은 key의 순서를 보장하지 않습니다. 즉, key를 삽입한 순서대로 value를 얻을 수 없습니다. 이러한 경우에는 다른 자료구조를 사용해야 합니다.
예제
다음은 leetcode의 Two sum이라는 문제입니다.
대충 요약하자면, 정수 타입인 배열 nums와 target이 주어지면 nums의 두 수의 합과 target이 일치할 때의 인덱스를 리턴해야 하는 문제입니다. 위 문제는 아래처럼 자바에서 이미 구현된 클래스인HashMap(일반적으로 자바에서는 HashMap이 Hashtable보다 더 나은 성능과 기능을 제공)을 활용하여 풀이가 가능합니다.
import java.util.*;
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> hash = new HashMap<>();
for(int i = 0 ; i<nums.length ; i++){
int complement = target - nums[i]; // 현재 반복중인 nums의 값과 target의 차
if(hash.containsKey(complement)){ // complement가 hash에 존재한다면 정답을 찾은 것
return new int[]{hash.get(complement),i};
}
hash.put(nums[i],i);
}
return new int[]{}; // 정답이 존재하지 않는 경우
}
}
Java
복사