Java에서 contains ()에 대한 가장 빠른 데이터 구조?

Java에서 contains ()에 대한 가장 빠른 데이터 구조?

---

contains ()에 대한 가장 빠른 작업을 수행하는 Java의 데이터 구조는 무엇입니까?

예 : 숫자 세트가 있습니다 {1, 7, 12, 14, 20 ...}

다른 임의의 숫자 x가 주어지면 x가 세트에 포함되어 있는지 여부에 대한 부울 값을 생성하는 가장 빠른 방법은 무엇입니까? ! contains ()의 확률은 약 5 배 더 높습니다.

모든 맵 구조가 o (1) 작업을 제공합니까? HashSet이 가장 빠른 방법입니까?

---

세트 (Hashset, enumset) 및 해시 (HashMap, linkedhash ..., idnetityhash ..) 기반 구현을 살펴보십시오. contains ()에 대해 O (1)이 있습니다.

이 치트 시트 는 큰 도움이됩니다.

---

상대적으로 밀도가 높은 숫자의 경우 BitSet을 사용하면 해시 세트보다 빠르고 훨씬 작습니다.

---

HashSet보다 빠른 유일한 데이터 구조는 Trove4J의 TIntHashSet 일 것입니다. 이것은 Integer Object를 사용할 필요가없는 프리미티브를 사용합니다.

정수의 수가 적 으면 존재하는 각 값이 "true"로 바뀌는 boolean []을 만들 수 있습니다. 이것은 O (1)입니다. 참고 : HashSet은 O (1)로 보장되지 않으며 O (log (log (N))) 일 가능성이 높습니다.

이상적인 해시 분포에 대해서만 O (1)을 얻습니다. 그러나 해시 된 버킷의 충돌이 발생할 가능성이 더 높으며 일부 조회에서는 둘 이상의 값을 확인해야합니다.

---

hashing (hash set)은 O (1)와 함께 가장 좋은 것입니다.

참고 URL : https://stackoverflow.com/questions/3267572/fastest-data-structure-for-contains-in-java