공부공간

Java Hashcode() 와 identityHashcode() 본문

SW기술면접

Java Hashcode() 와 identityHashcode()

개발자가될수있을까? 2021. 2. 28. 09:45

최근에 알고리즘 문제를 풀다가 조금 신기한 경우를 발견했다..

 

( 사실 내가 기초가 없어 자바는 new만 해주면 서로다른 Hashcode를 가지고 관리되는 줄 알았다)

 

내가 넣어준적 없는 List_B가 HashMap에 있다고 나온다..

 

그렇다면 HashMap은 객체의 어떤 값을 Key로 설정하여 Value 들을 관리할까 ??


1 ) HashMap Class 내부에서 자료들을 어떻게 관리할까 ?

 

Hashmap 내부의 get 메소드는 이런식이였다.

먼저, get은 hashmap에서 특정 객체를 뽑아올때, 특정 객체를 hash()의 인자로 넣고 그 결과를 getNode()를 호출시켜서 value가있으면 반환하는 로직으로 구성되어있다. 

 

Hashmap 내부의 put 메소드도 이런식이였다.

put도 마찬가지로 hash함수에 key를 통과시켜서 putVal한 결과를 반환하는 식이였다.

 

그렇다면 Hashmap.hash()는 어떻게 구성되어있을까 ?

간단하게 객체의 해쉬코드값( hashCode() )을 불러와서 적절한 비트 xor연산을 통해 int값을 반환하는것을 볼수있다.

즉 객체가 하나의 정수값으로 매핑이 되는과정이다. 다시 돌아와서 List_A와 List_B가 Hashmap에있다는것은 저 Key.hashCode()에서 넘어오는 값이 똑같다는 이야기인데, 최상위인 Object 클래스로 넘어가 hashCode()를 호출했을때 어떤 값이 지정되는지 확인해보자..

 

 

Object 클래스에서는 int 값을 리턴하고 이렇게 추가적으로 설명되어있다..

 

결론은, 실용적인이유로 distinct한 objects는 distinct한 integers를 반환한다고 써있다 !

( native 메소드는 stackoverflow.com/questions/18900736/what-are-native-methods-in-java-and-where-should-they-be-used 에서 내용확인 / 간단하게, 외부에서 불러오는거다 ) 

 

그럼 Object 클래스단에서는 다른 객체니까 다른 정수값을 주었다는 이야기인데..

왜 갑자기 List_A와 List_B가 같은 값을 가지게 되었을까 ? 

 

 

Object 클래스를 상속받은 ArrayList도 하나의 객체이니 ArrayList에서 오버라이딩할때 변경된건가 ?

 


2 ) List의 Hashcode는 어떻게 만들어 질까 ?

 

List의 Hashcode를 확인하기 위해 타고들어가봤다.

 

ArrayList 내부의 hashCode() 함수이다

범위기반으로 리스트를 돌면서 내부의 Wrapper Class의 해쉬코드값을 적절하게 연산을 통하여 하나의 정수값을 반환하는 것을 알수있다!

 

그럼 마지막으로 ArrayList안에 포함된 IntegerClass의 hashcode()는 어떻게 정의되어있을까 ? 

 

 

Integer Class 내부에서 오버라이드한 Hashcode 메소드 이다.

 

그냥 그 정수값을 리턴하는 것으로 알수 있다. 

 

이제 List_A와 List_B가 같은 이유가 Object 단에서는 다른 hashcode가 생성 되었었지만, 이를 구현한 ArrayList 클래스에서 hashcode() 메소드를 오버라이딩하면서 같아진 경우였다.

 

HashMap은 잘못없이 hashcode 값만으로 적절하게 자료들을 관리했기에 List_B가 Hashmap에 있다고 던진것이다 !

 

그렇다면, 원래 Object 클래스에 쓰여있던대로 객체마다 다른 Hashcode값은 확인 할 수 없을까 ?

 


3 ) System.identityhashcode() 

 

찾다보니 native 접근자로 외부에서 정의되어 사용되는 메소드가 있다.. 그만하라는 이야기인가..

 

다르게 hashcode값을 조회하는 방법은 System Class 내부의 identityHashcode 메소드의 인자로 객체를 넘겨주는 것이다.

 

추가적으로 identityHashCode도 완벽하게 독립적이지 못한다고한다. 

따라서 클래스를 생성할때에 Hashcode() 메소드를 적절하게 오버라이딩해서 사용하면 될것같다.

( 그 자료들을 관리하는 PK같은걸로 )

 

 

결론 )

 

1. 객체는 서로다른 Hashcode 값을 가지는게 맞다.

2. 하지만 이를 오버라이딩할때에 구현 방식에따라 조금씩 달라지기때문에, 우리가 생각하는 Hashcode의 역할을 수행하려면 오버라이딩을해서 직접 구현하는 것이 안전하다..

3. Hashmap은 객체의 Hashcode값으로 Treenode에 저장하기 때문에 잘못이없다 ! 

 

끝 !

 

4. 추가적으로 값을 기반으로 관리된다면, 알고리즘 풀면서 방문체크할때에 사용하면 될것같다 !

( 또한 값이 자주 변경되면 Hashcode 값도 계속 변경되어서 Hashmap에 들어가기때문에 잘 생각해야된다. )

 

풀었던 문제는 ) 

 

www.acmicpc.net/problem/9985

 

9985번: Missing Piece 2001

Remember those wacky number puzzles you used to win at birthday parties as a kid? Well, they're back, but this time with a digital twist. As with everything else, kids today are spoiled, having access to technology to make things easier for them. And why s

www.acmicpc.net

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
	public static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
	
	public static class node {
		ArrayList<Integer> al ;
		int y=0,x=0;
		node(){};
		node(int size){
			this.al = new ArrayList<>(size*size);
			for(int i=0;i<size*size;i++) {
				al.add(-1);
			}
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = null;
		StringBuilder sb = new StringBuilder();
		while( (str =br.readLine()) != null) {
			String[] sstr = str.split(" ");
			int M = Integer.parseInt(sstr[1]);
			int N = Integer.parseInt(sstr[2]);
			node map[] = new node[2]; 
			for(int i=0;i<2;i++) {
				map[i] = new node(M);
				for(int y=0;y<M;y++) {
					StringTokenizer st = new StringTokenizer(br.readLine());
					for(int x=0;x<M;x++) {
						String now = st.nextToken();
						if(now.equals("X")) {
							int index = y*M+x;
							map[i].y=y;
							map[i].x=x;
							map[i].al.remove(index);
							map[i].al.add(index,0);
						} else {
							int index = y*M+x;
							map[i].al.remove(index);
							map[i].al.add(index,Integer.parseInt(now));
						}
					}
				}
			}
		
			String end = br.readLine();
			HashMap<ArrayList<Integer>, Integer> hm[] = new HashMap[2];
			hm[0] = new HashMap<>();
			hm[1] = new HashMap<>();
			for(int i =0 ; i < 2 ; i ++) {
				ArrayDeque<node> dq = new ArrayDeque<>();
				hm[i].put(map[i].al, 0);
				dq.add(map[i]);
				for(int j =0; j<(N/2 + (N%2 & i));j++) {
					int size = dq.size();
					while(size>0) {
						size--;
						node now = dq.poll();
						for(int k=0;k<4;k++) {
							int nexty = now.y+dir[k][0];
							int nextx = now.x+dir[k][1];
							if(nexty>=0&&nextx>=0&&nexty<M&&nextx<M) {
								int pos = now.y*M+now.x;
								int npos = nexty*M+nextx;
								
								Collections.swap(now.al, pos, npos);
								if(!hm[i].containsKey(now.al)) {
									hm[i].put((ArrayList<Integer>) now.al.clone(), j+1);
									node next = new node(M);
									next.x = nextx;
									next.y = nexty;
									next.al = (ArrayList<Integer>) now.al.clone();
									dq.add(next);
								}
								Collections.swap(now.al, npos, pos);
							}
						}
					}
				}
			}
			
		
			int answer = 987654321;
			Set<ArrayList<Integer>> keys = hm[0].keySet();
			for (ArrayList<Integer> key : keys) {
				if(hm[1].containsKey(key)) {
					int res = hm[1].get(key)+ hm[0].get(key);
					answer = answer > res ? res : answer; 
				}
			}
			if(answer <=N) {
				sb.append("SOLVABLE WITHIN "+answer+" MOVES"+"\n\n");
			} else {
				sb.append("NOT SOLVABLE WITHIN "+N+" MOVES"+"\n\n");
			}
			
			
		}System.out.print(sb);
	}

}

'SW기술면접' 카테고리의 다른 글

2020 - 우리FIS 최종합격  (4) 2020.12.02
Comments