HashMap 검색 결과

해당 글 10건
marking 배열과 sparse array

1달 2주 정도만에 자료구조 포스팅으로 돌아왔습니다. 와아아~. 생각난 김에, 안드로이드의 sparse Array에 대한 이야기를 해 보도록 하겠습니다. 당장 android의 스파스 어레이를 구글에 검색해 보시면 HashMap 하고 비교하는 글도 많아요. 거기서 빠질 수 없는 주제는 성능 비교일 텐데요. 퍼포먼스 이야기는 여기서 굳이 하지 않겠습니다. 이 포스팅을 보신 다음에, 추가적인 질문을 통해서 생각을 해 보도록 합시다. sparse는, 분포된 정도가 적은, 희박한이라는 뜻을 가집니다. 이것이 array의 수식어가 되면 어떨까요? 희소 배열. 즉, 전체에서, 정말 중요한 몇 % 정도만 저장하고 있는 구조 정도로 생각하시면 됩니다. 그런데, 사실 수식어가 걸리는 대상이 더 중요합니다. 여기서, 걸리는..
자료알고/자료구조 2020. 6. 19. 00:34
java linkedhashmap : 해시맵과 비교해서 어떤 점이 오버헤드가 걸리는지 알아봅시다.

요새 이것 저것 코드를 보면서 궁금했던 점을 하나씩 채워나가고 있습니다. 그 중 하나는, LinkedHashMap입니다. 사용 방법은 많이 나와 있으니, 여기에서는 따로 언급하지 않겠습니다. 이 글에서는 HashMap과 다른 점이 무엇인지 보면서 어떤 자료구조가 어떤 연산에서 상대적으로 오버헤드가 많이 걸리는지 분석해 보도록 하겠습니다. 먼저 hashMap입니다. 간단하게 "AA", "AE", "BA", "BE", "DA"를 넣고, hashMap에 있는 모든 키를 순회하면서 출력하는 예제입니다. HashMap의 구조를 그려보면 아래와 같습니다. 삭제를 하기 위해서, 각 버킷에서 해당 Key를 찾아서 remove를 할 겁니다. 그리고 insert 연산을 수행하기 위해서 Key가 어느 번호의 버킷에 들어가는..
레퍼런스/분석 2020. 5. 21. 21:47
java의 hashtable 대신에 왜 다른 것을 권장할까요?

안녕하세요. chogahui05입니다. Java에는 HashTable이 있습니다. hash 기반의 자료구조를 동기화 했다고 생각하시면 편합니다. HashMap과 다른 부분 중 하나입니다. 먼저, 주요 필드들을 보도록 하겠습니다. table입니다. 이는, 무엇을 의미할까요? putVal 함수의 일부분입니다. tab에 table을 넣고 있습니다. 그리고 hash는 key 객체의 hashCode를 의미합니다. 이것과 무엇인가를 연산해서, index라는 값을 만들었습니다. 466번째 줄까지 보았을 때, index는 버킷 번호와 관련이 깊어 보입니다. 그리고 entry 값을 하나 받는데요. hashtable이나, hashmap은 키의 중복을 허용하지 않는 구조입니다. 그렇다면, 해당 버킷에 key가 있는지를 확인..
레퍼런스/분석 2020. 4. 3. 01:12
왜 java의 hashmap 클래스는 스레드 안전하지 않는가?

hashMap은 동기화가 된 클래스가 아닙니다. 그렇기 때문에, 두 Thread에서 같은 hashMap에 동시에 접근했을 때, 문제가 발생할 수 있습니다. 둘 다 write 연산을 수행할 때에도 문제가 발생할 겁니다. 그런데, 왜 문제가 될까요? 문제가 되는 시나리오가 없을까요? 그 시나리오는, 당황하면 쉽게 생각할 수 없습니다. 두 Thread가 있습니다. 이 Thread들은, 서로 다른 값의 Integer인, 6개의 Key 값을 넣습니다. 그러면 put 메서드를 실행을 하게 될 건데요. 어떠한 일이 벌어질까요? 저는, 12보다 작아질 수 있다고 답변했습니다. 그 말이 맞을까요? 먼저 hashmap을 간단하게 보도록 하겠습니다. 3개의 static 변수만 봅시다. DEFAULT_INITIAL_CAPAC..
OS/이론 2020. 3. 25. 00:40
java hashset은 key의 해쉬 코드가 모두 같을 때 최악 복잡도가 어떻게 될까요?

저번에, 왜 equals를 구현하면 왜 hashCode를 같이 구현해야 하는지에 대해서 설명을 했습니다. hash 계열의 자료구조 때문에 그렇다고 했었습니다. 그렇지 않으면 어떻게 동작하는지는 여기를 참고하시면 좋겠습니다. 이 내용에 대해서 숙지하셨다고 가정하고 진행하도록 하겠습니다. 면접 질문에서 간혹 가다가 등장하는지는 잘 모르겠습니다만, 어떠한 객체의 hashCode 값이 같은 것들을 모두 hashSet에 넣을 때, 어떤 일이 벌어지는지는 꽤 중요한 문제 중 하나일 겁니다. 사실, 우리는 그렇게 바보같이 구현할 일이 없습니다. 그렇지만, 저는 이에 대해서 포스팅 하도록 하겠습니다. 먼저 Java 8에서부터, hashMap은 버킷에 8개 이상 달려있을 때, Balanced Tree로 변환이 된다는 것..
레퍼런스/분석 2019. 12. 18. 22:35