다르다.

몰랐다.

그래서

한참을

돌았다.

그런데.

똑같네?

다른줄

알았다.


이게 무슨 소리지..

처음엔 내가 잘못 알고 있나? 싶었다. 


어떤 숫자가 있는지 없는지만 확인하면 되는 로직에 HashSet<Integer>를 사용했다.

거기에 0부터 24까지의 정수를 추가했다고 하면,

위와 같은 코드가 될 것이다.


그리고 저 아래와 같은 코드를 실행하면 출력 결과가 true인 것은 자명하다.


System.out.println(set.contains(1));


그렇다면 1 대신에 1l 또는 (long)1을 넣으면 true일 것이라고 예상했다.

헌데 결과는 false 이다.

내가 아는 바로는 int 의 표현 범위 내에서 int 와 long은 같은 hashCode를 가진다.

그래서 확인을 해봤다.


System.out.println(Integer.hashCode(1));

System.out.println(Long.hashCode(1));


실행 결과는 생각한대로 둘 다 1이다. int 범위 내의 어떤 값이든 그렇다.

그리고 정수 기본타입은 자신의 값이 곧 자신의 해시코드라고 알고 있었는데,

HashSet 이란 놈이 이렇게 배신을 할 줄이야.

이름만 보면 Set에 포함된 엘리먼트들의 유일성을 Hash 값으로 판단한단 말이 아닌가?


HashSet의 코드를 뜯어보니 HashSet은 내부적으로 엘리먼트의 저장을 HashMap을 사용한다.

왜인지는 모르겠다. 코드의 중복을 줄이기 위해서인지? 구현 편의인지.

HashMap은 Entry를 사용하니까 엘리먼트 하나를 저장하는 것보다 키, 밸류를 저장하는 게 손해아닌가..?

HashSet에서는 HashMap의 Entry의 value 값에 빈 Object객체를 넣는다.

빈 Object 객체는 static 변수로 선언되어 있다.

(private static final Object PRESENT = new Object();)


어쨌거나 어디서부터 잘못 이해하고 있는지 확인 하기 위해서 HashSet에서 contains 메서드가 호출하는 HashMap.containsKey 메서드를 살펴봤다.

containsKey에서는 map의 get메서드가 호출하는 getEntry(key)를 호출하고, key를 이용해서 Entry를 가져오지 못하면 null일 때 containsKey는 false가 되고 있으면 true가 된다.

그럼 getEntry에서는 무엇을 하느냐? key의 해시값을 이용해서 HashMap이 가지고 있는 hashSeed값과 적절한 연산을 통해 해시 값을 만들고, 이 해시를 이용해서 해시 테이블에 있는 엔트리를 찾는다.


결국 hash값으로 찾는게 맞단 소리고, HashMap의 hash 메서드의 인자를 long과 int 타입으로 테스트해보니 값이 같을 때 같은 값이 나온다.


여기까지의 결론으로는 결국 set.contains(1) 이나, set.contains((long)1) 이나 같은 결과를 보여야 하는게 정상인데..

왜 false라는 값이 나올까..?? map과 set을 좀 더 파헤쳐봐야겠다.



검색 중 Why you should not user HashSet/HashMap for Integer number 글 발견..

관련있는 글

인공지능 과제에서 인덱싱을 하면서 무심코 HashMap을 사용했는데,

다른 조의 시연을 보니 인덱싱에 상당한 시간이 소요되었다.


갑자기 궁금증이 생겨서 세 컬렉션의 속도를 비교하게 되었다.

테스트 엘리먼트는 Integer 인스턴스 5,000,000(5백만개)를 이용하여 수행하였다.

탐색과 삭제에서는 균등하게 떨어진 4990개의 데이터를 이용하였다.


테스트 결과 :

5000000개의 인스턴스 생성 시간 0.548829807초


HashMap Test

입력 소요 시간  2.415268645초

탐색 소요 시간 0.002399381초

삭제 소요 시간 0.002615092초


ArrayList

입력 소요 시간  0.381054002초

탐색 소요 시간 1.99475E-4초

삭제 소요 시간 137.231368119초


LinkedList

입력 소요 시간  1.503839756초

탐색 소요 시간 52.905209243초

삭제 소요 시간 52.587791295초



HashMap의 경우는 입력되는 시간을 제외하면 우수한 성능을 보였고,

(탐색과 삭제 시에 인덱스가 아닌 키값으로 하였음)


ArrayList 의 경우에는 내부적으로 배열을 쓰는 컬렉션 답게 탐색에서는 매우 우수한 속도를 보였지만

삭제 시에 배열의 구조가 변경되므로 매우 느린 속도를 보였다.


LinkedList는.. 탐색, 삭제 모두 순차 탐색을 하므로(실제로 이중 연결 링크드리스트로 되어있고, Head, Rear 포인터를 이용해서, 탐색하려고 하는 인덱스와 리스트 크기의 반과 비교해서 인덱스가 작은 경우 앞에서부터 탐색하고, 큰 경우 뒤에서부터 탐색하도록 되어있어 평균적으로 n / 2의 시간 복잡도를 가진다.) 많이 느렸다. -_-



따라서 HashMap은 Key, Value 쌍을 가지는 데이터를 관리할 때 용이하고,

ArrayList는 데이터가 입력 되고 삭제가 빈번하지 않은 경우에 사용하면 되고,

Linkedlist는 Queue와 같이 Head와 Read와 가까이에서 탐색, 삭제가 이뤄지는 경우에 쓰면 좋을 듯 하다.



테스트에 사용한 코드는 아래와 같습니다. 참고 하실 분은 아래의 소스를 사용하시면 됩니다.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class TestCode {
	static Integer[] testArray = new Integer[5000000];
	Integer[] values = new Integer[4990];

	public void hashMapTest() {
		long start = System.nanoTime();

		HashMap hashmap = new HashMap();
		for(Integer integer : testArray){
			hashmap.put(integer, integer);
		}
		
		long end = System.nanoTime();
		
		System.out.println("\nHashMap Test");
		System.out.println("\t입력 소요 시간  " + second(start, end) + "초");
		
		start = System.nanoTime();
		for(Integer value : values){
			hashmap.get(value);
		}		
		end = System.nanoTime();
		System.out.println("\t탐색 소요 시간 " + second(start, end) + "초");
		
		start = System.nanoTime();
		for(Integer value : values){
			hashmap.remove(value);
		}
		end = System.nanoTime();
		System.out.println("\t삭제 소요 시간 " + second(start, end) + "초");
	}
	
	public void arrayListTest(){
		long start = System.nanoTime();
		
		ArrayList arrayList = new ArrayList();
		for(Integer integer : testArray){
			arrayList.add(integer);
		}
		
		long end = System.nanoTime();
		
		System.out.println("\nArrayList");
		System.out.println("\t입력 소요 시간  " + second(start, end) + "초");
		
		start = System.nanoTime();
		for(Integer value : values){
			arrayList.get(value);
		}		
		end = System.nanoTime();
		System.out.println("\t탐색 소요 시간 " + second(start, end) + "초");
		
		start = System.nanoTime();
		for(Integer value : values){
			arrayList.remove(value);
		}
		end = System.nanoTime();
		System.out.println("\t삭제 소요 시간 " + second(start, end) + "초");
	}
	
	public void linkedListTest(){
		long start = System.nanoTime();
		
		List linkedList = new LinkedList();
		for(Integer integer : testArray){
			linkedList.add(integer);
		}
		
		long end = System.nanoTime();
		
		System.out.println("\nLinkedList");
		System.out.println("\t입력 소요 시간  " + second(start, end) + "초");
		start = System.nanoTime();
		for(int value : values){
			linkedList.get(value);
		}		
		end = System.nanoTime();
		System.out.println("\t탐색 소요 시간 " + second(start, end) + "초");
		
		start = System.nanoTime();
		for(int value : values){
			linkedList.remove(value);
		}
		end = System.nanoTime();
		System.out.println("\t삭제 소요 시간 " + second(start, end) + "초");
	}


	private void prepare() {
		long start = System.nanoTime();
		for (int i = 0; i < testArray.length; i++) {
			testArray[i] = i;
		}
		long end = System.nanoTime();
		
		ArrayList temp = new ArrayList(1000);
		for(int i = 0 ; i < 4990 ; i++){
			temp.add(i * 1000);
		}
		temp.toArray(values);
		
		
		System.out.println(testArray.length + "개의 인스턴스 생성 시간 " +
				second(start, end) + "초");
		
	}
	
	private double second(long start, long end){
		return (end - start) / Math.pow(10, 9);
	}

	public void start() {
		prepare();
		hashMapTest();
		arrayListTest();
		linkedListTest();
	}

	public static void main(String[] args) {
		TestCode test = new TestCode();
		test.start();
	}
}


'밤을 지새다 > Java' 카테고리의 다른 글

Java 8 메서드 파라미터의 이름 얻기  (2) 2015.04.30
int 와 long 의 해시 값은 다르다?  (0) 2014.03.15
이클립스 환경에서 AWT에서 한글이 깨질 때  (0) 2012.05.16
Java PriorityQueue  (0) 2012.05.07
Java StAX Event  (0) 2012.05.01
  1. 잘봤습니다. 2013.12.15 01:25

    Hashmap은 중복된 값이 들어오면 이전의 값이 새로 들어온 값으로 바뀝니다.
    즉 입력하는 과정에서 계속 중복되므로 결국에 size는 1이 됩니다.
    이는 탐색속도를 측정할때 영향을 주게됩니다. (결국 size가 1인 map에서 탐색하니 속도가 빠르게 나올껍니다.)

    • 마음이 뛰다 2013.12.16 13:28 신고

      글의 제일 위쪽에 보시면
      테스트 엘리먼트는 Integer 인스턴스 5,000,000(5백만개)를 이용하여 수행하였다.
      탐색과 삭제에서는 균등하게 떨어진 4990개의 데이터를 이용하였다.
      라고 써두었습니다. 키를 같은 값으로 하지는 않았습니다.

  2. HELLO 2014.02.25 15:01

    ArrayList가 배열을 사용해서 검색에 빠르다고는 하나 아무래도 HashMap이 빠르겠죠. 잘보았습니다.

    • 마음이 뛰다 2014.04.17 15:55 신고

      둘다 O(1)이긴 하나, 연산 자체가 직접 접근과 해시 계산 후 접근이니,
      접근 자체는 ArrayList가 빠르지요. 삽입, 삭제, 검색 등의 연산이 각각 특성화된 것들이 있으니 무엇이 빠르다, 느리다 보다는 무엇을 어디에 적절하게 써야 하는지를 알아야 할 것 같습니다 :)

    • hhh 2017.10.31 13:47

      HashMap은 get 함수 자체로, key에 대한 value를 검색해서 가져오고, ArrayList는 get을 사용할 경우에는 index를 기준으로 가져오는 것입니다.
      ArrayList는 String 혹은 별도의 Object에 대하여 많이 사용하는데, index를 모를 경우에는 별도로 검색하는 부분을 구현해주어야하고 그러면 검색은 HashMap에 비해서는 많이 느려질겁니다.

+ Recent posts