해시테이블 - 연습 문제

문제1

// Practice1
// 해시 테이블을 이용한 수 찾기
// 주어진 첫 번째 배열을 이용하여 해시 테이블을 초기화 한 후
// 두 번째 배열이 주어졌을 때 해당 배열 내 데이터가 해시 테이블에 있는지 확인하는 코드를 작성하세요.

// 입출력 예시)
// 배열1: 1, 3, 5, 7, 9
// 배열2: 1, 2, 3, 4, 5
// 출력: True, False, True, False, True

 

구현 코드

import java.util.Hashtable;

public class Practice1 {
    public static void solution(int[] arr1, int[] arr2) {
        Hashtable<Integer, Integer> ht = new Hashtable<>();

        for (int i = 0; i < arr1.length; i++) {
            ht.put(arr1[i], arr1[i]);
        }

        for (int i = 0; i < arr2.length; i++) {
            if (ht.containsKey(arr2[i])) {
                System.out.println("True");
            } else {
                System.out.println("False");
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Test code
        int[] arr1 = {1, 3, 5, 7, 9};
        int[] arr2 = {1, 2, 3, 4, 5};
        solution(arr1, arr2);

    }
}

 

출력 결과

True
False
True
False
True

 

---

문제2

// Practice2
// 정수형 배열 nums 와 target 이 주어졌을 때,
// nums 에서 임의의 두 수를 더해 target 을 구할 수 있는지 확인하는 프로그램을 작성하세요.
// 두 수 의 합으로 target 을 구할 수 있으면 해당 값의 index 를 반환하고,
// 없는 경우 null 을 반환하세요.

// 입출력 예시
// nums: 7, 11, 5, 3
// target: 10
// 출력: 0, 3

// nums: 8, 3, -2
// target: 6
// 출력: 0, 2

이중 for문을 돌려서 구현할 수도 있지만 시간복잡도가 O(n^2)가 됨 => 비효율적인 알고리즘

=> 해시테이블로 문제 코드 구현

구현 코드

import java.util.Arrays;
import java.util.Hashtable;

public class Practice2 {
    public static int[] solution(int[] numbers, int target) {
        int[] result = new int[2];
        Hashtable<Integer, Integer> ht = new Hashtable<>();

        for (int i = 0; i < numbers.length; i++) {
            if (ht.containsKey(numbers[i])) {
                result[0] = ht.get(numbers[i]);
                result[1] = i;
                return result;
            }
            ht.put(target - numbers[i], i);
        }
        return null;
    }

    public static void main(String[] args) {
        // Test code
        int[] nums = {7, 11, 5, 3};
        System.out.println(Arrays.toString(solution(nums, 10)));

        nums = new int[]{8, 3, -2};
        System.out.println(Arrays.toString(solution(nums, 6)));

        nums = new int[]{1, 2, 3};
        System.out.println(Arrays.toString(solution(nums, 12)));
    }
}

for (int i = 0; i < numbers.length; i++) {
    if (ht.containsKey(numbers[i])) {
        result[0] = ht.get(numbers[i]);
        result[1] = i;
        return result;
    }
    ht.put(target - numbers[i], i);

ht 해시 테이블에 for문을 돌면서 각 인덱스 별 target과 인덱스 별로

차(target-인덱스 값)를 저장하며 =>  (key: 차, value: 인덱스) 

합이 되는 값이 있는지 확인하면서 배열을 만들어감

=> 합이 되는 값이 발견되면 결과를 반환할 수 있도록!!

출력 결과

[0, 3]
[0, 2]
null

 

---

 

Hashtable 과 HashMap 비교

//Hashtable
Hashtable<Integer, Integer> ht = new Hashtable<>();
ht.put(0, 10);
System.out.println(ht.get(0)); // 10

// HashMap
HashMap<Integer, Integer> hm = new HashMap<>();
hm.put(0, 10);
System.out.println(hm.get(0)); // 10

// 두 가지 모두 Map 인터페이스로 구현된 class 이기 때문에
// 다형성 부분으로 보면 Map 을 이용하여 값을 받아올 수 있음
Map<Integer, Integer> map1 = ht;
Map<Integer, Integer> map2 = hm;
System.out.println(map1.get(0)); // 10
System.out.println(map2.get(0)); // 10

 

Hashtable 과 HashMap 공통점, 차이점

공통점

• 둘 다 Map 인터페이스를 구현한 것

차이점

// 차이점

// Hashtable=> key로 null을 이용한 키값을 이용할 수 없음
ht.put(null, -999);
System.out.println(ht.get(null)); // 에러 발생
//Exception in thread "main" java.lang.NullPointerException: Cannot invoke "Object.hashCode()" because "key" is null
//  at java.base/java.util.Hashtable.put(Hashtable.java:481)
//  at Practice3.main(Practice3.java:30)

// HashtMap=> key로 null을 이용한 키값을 사용 가능
hm.put(null, -999);
System.out.println(hm.get(null)); //-999

• Key에 Null 사용 여부
  • Hashtable은 사용 불가
  • HashMap은 사용 가능
• Thread-safe
  • Hashtable은 사용 가능(멀티 스레드 환경에서 우수)
  • HashMap은 사용 불가(싱글 스레드 환경에서 우수)
  • 참고) synchronizedMap, ConcurrentHashMap을 이용하면 HashMap을 Thread-safe하게 사용 가능

 

** 강의에서 잠깐 언급된 Thread에 대해  간단히 정리해보자면 (추후 관련 내용응 정리 해봐야 할 듯)

Thread =>

컴퓨터 CPU에 프로레서가 존재함

프로세서에는 작업 처리하는 스레드가 존재

    -시간을 계산해서 화면에 띄워준다던지

    -사용자로부터 값을 입력받아 계산을 한다던지..

 

멀티스레드라 함은 동시에 일을 진행하는것이 아니고 프로세서가 일을 할 수 있는 시간 안에서

어떤 시간에는 어떤 작업을 할지 할당됨 =>  운영체제가 어떻게 스케줄링 하느냐에 따라 다름

(우리가 볼 땐 동시 진행처럼 보이긴 함 =>이는 멀티 프로세싱 (병렬처리))

anyway.. 

시간마다 어떤 작업이 될 지 정해지는데 근데 이 작업들은 하나를 다 수행하고 다음 단계로 가는 것이 아니라

ex) 1번 작업 / 2번 작업 / 3번 작업이 있을 때 => 1번 작업을 하다가 2번 작업으로 갔다가 다시 1번 작업을 수행하기도 함

int a라는 변수가 있는데 1번에서는 a가 5인데 2번에서는a를 10으로 출력 중임

=> 1번 작업을 하다가 2번 작업으로 넘어가서 a를 5로 바꾸고 다시 1번으로 돌아와서 작업 수행 후

2로 넘어가서 a를 출력하게 되면 원하던 10이 아닌 5가 출력될 수도 있음 => Thread-unsafe한 상황

 

=>그래서 이를 해결하기 위해  2번 수행하기 전에 Lock을 통해 공유자원을 제어하거나 다른 여러 방법 들이 있다

Thread가 공유 메모리에 존재하는 int a 변수를 1번 thread가 사용할 때 잠시 lock을 해줌  =>   스레드 2가 int a를 사용하더라도 스레드1에선 침범 불가능해지게 됨 2수행 후엔 unlock

 

Thread-safe

멀티 쓰레드 프로그래밍에서, 어떤 공유 자원에 여러 쓰레드가 동시에 접근해도, 프로그램 실행에 문제가 없는 상태