더 빠른 해시 조회 또는 이진 검색?
최적의 성능으로 반복되는 동시 조회가 필요한 정적 개체 집합 (한 번로드 된 경우 거의 변경되지 않는다는 점에서 정적)이 주어지면 어떤 것이 더 낫 HashMap습니까, 아니면 일부 사용자 지정 비교기를 사용하는 이진 검색이있는 배열입니까?
대답은 객체 또는 구조체 유형의 함수입니까? 해시 및 / 또는 동등한 기능 성능? 해시 고유성? 목록 크기? Hashset크기 / 세트 크기?
제가보고있는 세트의 크기는 정보가 유용 할 경우 500k에서 10m까지 가능합니다.
C # 답변을 찾고 있지만 진정한 수학적 답변은 언어에 있지 않다고 생각하므로 해당 태그를 포함하지 않습니다. 그러나주의해야 할 C # 특정 사항이있는 경우 해당 정보가 필요합니다.
좋아, 내가 짧게해볼 게.
C # 짧은 대답 :
두 가지 다른 접근 방식을 테스트합니다.
.NET은 한 줄의 코드로 접근 방식을 변경할 수있는 도구를 제공합니다. 그렇지 않으면 System.Collections.Generic.Dictionary를 사용하고 초기 용량으로 큰 수로 초기화해야합니다. 그렇지 않으면 GC가 오래된 버킷 배열을 수집하기 위해 수행해야하는 작업으로 인해 항목을 삽입하는 나머지 인생을 통과하게됩니다.
더 긴 답변 :
해시 테이블에는 거의 일정한 조회 시간이 있으며 실제 세계에서 해시 테이블의 항목에 도달하는 데 해시를 계산할 필요가 없습니다.
항목을 얻기 위해 해시 테이블은 다음과 같은 작업을 수행합니다.
- 키의 해시 가져 오기
- 해당 해시의 버킷 번호를 가져옵니다 (일반적으로 map 함수는 다음과 같습니다. 버킷 = 해시 % bucketsCount).
- 해당 버킷에서 시작하여 각 키를 추가하려는 항목 중 하나와 비교하는 항목 체인 (기본적으로 동일한 버킷을 공유하는 항목 목록이며 대부분의 해시 테이블은이 버킷 / 해시 충돌 처리 방법을 사용함)을 탐색합니다. 포함 된 경우 삭제 / 업데이트 / 확인합니다.
조회 시간은 해시 함수가 얼마나 "좋은지"(스팸이 얼마나 적은지) 그리고 빠른지, 사용중인 버킷 수 및 키 비교자가 얼마나 빠른지에 따라 달라지며 항상 최상의 솔루션은 아닙니다.
더 좋고 더 깊은 설명 : http://en.wikipedia.org/wiki/Hash_table
매우 작은 컬렉션의 경우 그 차이는 무시할 수 있습니다. 범위 (500k 항목)의 낮은 끝에서 많은 조회를 수행하는 경우 차이를보기 시작합니다. 이진 검색은 O (log n)이되고 해시 검색은 O (1), amortized가 됩니다. 그것은 진정으로 상수와 같지는 않지만 바이너리 검색보다 더 나쁜 성능을 얻으려면 여전히 끔찍한 해시 함수가 있어야합니다.
( "끔찍한 해시"라는 말은 다음과 같은 의미입니다.
hashCode()
{
return 0;
}
예, 그 자체로는 엄청나게 빠르지 만 해시 맵이 연결된 목록이됩니다.)
ialiashkevich 는 두 방법을 비교하기 위해 배열과 사전을 사용하여 C # 코드를 작성했지만 키에 Long 값을 사용했습니다. 조회하는 동안 실제로 해시 함수를 실행하는 것을 테스트하고 싶었 기 때문에 해당 코드를 수정했습니다. 문자열 값을 사용하도록 변경했고, 프로파일 러에서 더 쉽게 볼 수 있도록 채우기 및 조회 섹션을 자체 메서드로 리팩터링했습니다. 비교의 포인트로 Long 값을 사용하는 코드도 남겼습니다. 마지막으로 사용자 지정 이진 검색 기능을 제거하고 Array클래스 에서 사용했습니다 .
그 코드는 다음과 같습니다.
class Program
{
private const long capacity = 10_000_000;
private static void Main(string[] args)
{
testLongValues();
Console.WriteLine();
testStringValues();
Console.ReadLine();
}
private static void testStringValues()
{
Dictionary<String, String> dict = new Dictionary<String, String>();
String[] arr = new String[capacity];
Stopwatch stopwatch = new Stopwatch();
Console.WriteLine("" + capacity + " String values...");
stopwatch.Start();
populateStringArray(arr);
stopwatch.Stop();
Console.WriteLine("Populate String Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
populateStringDictionary(dict, arr);
stopwatch.Stop();
Console.WriteLine("Populate String Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
Array.Sort(arr);
stopwatch.Stop();
Console.WriteLine("Sort String Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchStringDictionary(dict, arr);
stopwatch.Stop();
Console.WriteLine("Search String Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchStringArray(arr);
stopwatch.Stop();
Console.WriteLine("Search String Array: " + stopwatch.ElapsedMilliseconds);
}
/* Populate an array with random values. */
private static void populateStringArray(String[] arr)
{
for (long i = 0; i < capacity; i++)
{
arr[i] = generateRandomString(20) + i; // concatenate i to guarantee uniqueness
}
}
/* Populate a dictionary with values from an array. */
private static void populateStringDictionary(Dictionary<String, String> dict, String[] arr)
{
for (long i = 0; i < capacity; i++)
{
dict.Add(arr[i], arr[i]);
}
}
/* Search a Dictionary for each value in an array. */
private static void searchStringDictionary(Dictionary<String, String> dict, String[] arr)
{
for (long i = 0; i < capacity; i++)
{
String value = dict[arr[i]];
}
}
/* Do a binary search for each value in an array. */
private static void searchStringArray(String[] arr)
{
for (long i = 0; i < capacity; i++)
{
int index = Array.BinarySearch(arr, arr[i]);
}
}
private static void testLongValues()
{
Dictionary<long, long> dict = new Dictionary<long, long>(Int16.MaxValue);
long[] arr = new long[capacity];
Stopwatch stopwatch = new Stopwatch();
Console.WriteLine("" + capacity + " Long values...");
stopwatch.Start();
populateLongDictionary(dict);
stopwatch.Stop();
Console.WriteLine("Populate Long Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
populateLongArray(arr);
stopwatch.Stop();
Console.WriteLine("Populate Long Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchLongDictionary(dict);
stopwatch.Stop();
Console.WriteLine("Search Long Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchLongArray(arr);
stopwatch.Stop();
Console.WriteLine("Search Long Array: " + stopwatch.ElapsedMilliseconds);
}
/* Populate an array with long values. */
private static void populateLongArray(long[] arr)
{
for (long i = 0; i < capacity; i++)
{
arr[i] = i;
}
}
/* Populate a dictionary with long key/value pairs. */
private static void populateLongDictionary(Dictionary<long, long> dict)
{
for (long i = 0; i < capacity; i++)
{
dict.Add(i, i);
}
}
/* Search a Dictionary for each value in a range. */
private static void searchLongDictionary(Dictionary<long, long> dict)
{
for (long i = 0; i < capacity; i++)
{
long value = dict[i];
}
}
/* Do a binary search for each value in an array. */
private static void searchLongArray(long[] arr)
{
for (long i = 0; i < capacity; i++)
{
int index = Array.BinarySearch(arr, arr[i]);
}
}
/**
* Generate a random string of a given length.
* Implementation from https://stackoverflow.com/a/1344258/1288
*/
private static String generateRandomString(int length)
{
var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
var stringChars = new char[length];
var random = new Random();
for (int i = 0; i < stringChars.Length; i++)
{
stringChars[i] = chars[random.Next(chars.Length)];
}
return new String(stringChars);
}
}
다음은 여러 크기의 컬렉션을 사용한 결과입니다. (시간은 밀리 초 단위입니다.)
500000 긴 값 ...
긴 사전 채우기 : 26
긴 배열 채우기 : 2
긴 사전
검색 : 9 긴 배열 검색 : 80500000 문자열 값 ...
문자열 배열 채우기 : 1237
문자열 사전 채우기 : 46
문자열 배열 정렬 : 1755
문자열 사전
검색 : 27 문자열 배열 검색 : 15691000000 Long 값 ...
Long 사전 채우기 : 58
Long 배열 채우기 : 5
Long 사전
검색 : 23 Long 배열 검색 : 1361000000 문자열 값 ...
문자열 배열 채우기 : 2070
문자열 사전 채우기 : 121
문자열 배열 정렬 : 3579
문자열 사전
검색 : 58 문자열 배열 검색 : 32673000000 Long 값 ...
Long 사전 채우기 : 207
Long 배열 채우기 : 14
Long 사전
검색 : 75 Long 배열 검색 : 4353000000 문자열 값 ...
문자열 배열 채우기 : 5553
문자열 사전 채우기 : 449
문자열 배열 정렬 : 11695
문자열 사전
검색 : 194 문자열 배열 검색 : 1059410000000 Long 값 ...
Long 사전 채우기 : 521
Long 배열 채우기 : 47
Long 사전
검색 : 202 Long 배열 검색 : 118110000000 문자열 값 ...
문자열 배열 채우기 : 18119
문자열 사전 채우기 : 1088
문자열 배열 정렬 : 28174
문자열 사전
검색 : 747 문자열 배열 검색 : 26503
비교를 위해 다음은 프로그램의 마지막 실행에 대한 프로파일 러 출력입니다 (1000 만 개의 레코드 및 조회). 관련 기능을 강조했습니다. 위의 스톱워치 타이밍 메트릭과 거의 일치합니다.
사전 조회가 이진 검색보다 훨씬 빠르며 (예상대로) 컬렉션이 클수록 차이가 더 뚜렷하다는 것을 알 수 있습니다. 따라서 합리적인 해싱 기능이있는 경우 (충돌이 거의없이 상당히 빠름) 해시 조회는이 범위의 컬렉션에 대한 이진 검색을 능가해야합니다.
Bobby, Bill 및 Corbin의 답변은 잘못되었습니다. O (1)은 고정 / 제한 n에 대해 O (log n)보다 느리지 않습니다.
log (n)은 일정하므로 일정 시간에 따라 달라집니다.
느린 해시 함수의 경우 md5에 대해 들어 본 적이 있습니까?
기본 문자열 해싱 알고리즘은 아마도 모든 문자에 영향을 미치며 긴 문자열 키의 평균 비교보다 쉽게 100 배 느릴 수 있습니다. 거기 있었어요.
(부분적으로) 기수를 사용할 수 있습니다. 거의 동일한 크기의 256 개 블록으로 나눌 수 있다면 2k에서 40k 이진 검색을보고있는 것입니다. 그것은 훨씬 더 나은 성능을 제공 할 것입니다.
너무 많은 사람들이 이해하지 못하는 것을 투표했습니다.
이진 검색 정렬 된 집합에 대한 문자열 비교는 매우 흥미로운 속성을 가지고 있습니다. 대상에 가까울수록 속도가 느려집니다. 처음에는 첫 번째 문자에서 중단되고 마지막에는 마지막에만 중단됩니다. 그들에게 일정한 시간을 가정하는 것은 올바르지 않습니다.
이 질문에 대한 유일한 합리적인 대답은 다음과 같습니다. 데이터의 크기, 데이터의 형태, 해시 구현, 이진 검색 구현 및 데이터가있는 위치 (질문에 언급되지 않았더라도)에 따라 다릅니다. 몇 가지 다른 답변이 그렇게 많이 말하므로 이것을 삭제할 수 있습니다. 그러나 피드백에서 배운 것을 원래 답변과 공유하는 것이 좋을 수 있습니다.
- " 해시 알고리즘은 O (1)이고 이진 검색은 O (log n)입니다. "-주석에서 언급했듯이 Big O 표기법은 속도가 아니라 복잡성을 추정합니다. 이것은 절대적으로 사실입니다. 알고리즘의 시간 및 공간 요구 사항을 파악하기 위해 일반적으로 복잡성을 사용한다는 점은 주목할 가치가 있습니다. 따라서 복잡성이 속도와 엄격하게 동일하다고 가정하는 것은 어리석은 일이지만 마음 속에 시간이나 공간없이 복잡성을 추정하는 것은 드문 일입니다. 내 추천 : Big O 표기법을 피하십시오.
- 나는 " n이 무한대에 가까워지면 ..." 이라고 썼다 .-이것은 내가 대답에 포함시킬 수 있었던 가장 멍청한 것에 관한 것이다. 인피니티는 당신의 문제와 관련이 없습니다. 상한선 인 천만을 언급하셨습니다. 무한대를 무시하십시오. 논평자들이 지적했듯이, 매우 큰 숫자는 해시와 관련된 모든 종류의 문제를 일으킬 것입니다. (매우 큰 숫자는 이진 검색을 공원에서 산책으로 만들지 않습니다.) 제 권장 사항 : 무한을 의미하지 않는 한 무한대를 언급하지 마십시오.
- 또한 주석에서 : 기본 문자열 해시를 조심하십시오 (문자열을 해시합니까? 당신은 언급하지 않습니다.), 데이터베이스 색인은 종종 b- 트리 (생각할만한 음식)입니다. 내 추천 : 모든 옵션을 고려하십시오. 구식 트라이 (문자열 저장 및 검색 용) 또는 R- 트리 (공간 데이터 용) 또는 MA-FSA (최소 비순환 유한 상태 오토 마톤-작은 스토리지 풋 프린트) 와 같은 다른 데이터 구조 및 접근 방식을 고려하십시오 .
주석을 감안할 때 해시 테이블을 사용하는 사람들이 혼란 스럽다고 가정 할 수 있습니다. 해시 테이블은 무모하고 위험합니까? 이 사람들이 미쳤나요?
그렇지 않다는 것이 밝혀졌습니다. 이진 트리가 특정 항목 (순서대로 데이터 순회, 저장 효율성)에능한 것처럼 해시 테이블도 빛을 발할 순간이 있습니다. 특히 데이터를 가져 오는 데 필요한 읽기 수를 줄이는 데 매우 유용 할 수 있습니다. 해시 알고리즘은 위치를 생성하고 메모리 또는 디스크에서 바로 이동할 수 있으며 이진 검색은 각 비교 중에 데이터를 읽고 다음에 읽을 내용을 결정합니다. 각 읽기는 CPU 명령보다 훨씬 더 느린 캐시 미스 가능성이 있습니다.
해시 테이블이 이진 검색보다 낫다는 것은 아닙니다. 그들은 아니야. 또한 모든 해시 및 이진 검색 구현이 동일하다고 제안하는 것도 아닙니다. 그들은 아니야. 요점이 있다면, 두 가지 접근 방식 모두 이유가 있습니다. 귀하의 필요에 가장 적합한 것을 결정하는 것은 귀하에게 달려 있습니다.
원래 답변 :
해시 알고리즘은 O (1)이고 이진 검색은 O (log n)입니다. 따라서 n이 무한대에 가까워지면 이진 검색에 비해 해시 성능이 향상됩니다. 마일리지는 n, 해시 구현 및 이진 검색 구현에 따라 다릅니다.
O (1)에 대한 흥미로운 토론 . 의역 :
O (1)은 즉각적인 것을 의미하지 않습니다. 이는 n의 크기가 커도 성능이 변하지 않음을 의미합니다. 아무도 사용하지 않을 정도로 느리고 여전히 O (1) 인 해싱 알고리즘을 설계 할 수 있습니다. 그러나 .NET / C #은 비용이 많이 드는 해싱으로 고통받지 않는다고 확신합니다.;)
개체 집합이 진정으로 정적이고 변경되지 않는 경우 완벽한 해시 를 사용하여 O (1) 성능을 보장 할 수 있습니다. 나는 gperf 가 몇 번 언급하는 것을 보았지만 직접 사용할 기회는 없었습니다.
이진 검색은 최악의 경우 특성이 더 좋지만 해시는 일반적으로 더 빠릅니다. 해시 액세스는 일반적으로 레코드가 들어갈 "버킷"을 결정하기 위해 해시 값을 가져 오는 계산이므로 성능은 일반적으로 레코드가 얼마나 균등하게 분산되는지와 버킷을 검색하는 데 사용되는 방법에 따라 달라집니다. 버킷을 통한 선형 검색을 사용하는 잘못된 해시 함수 (레코드가 많은 버킷 몇 개 남김)는 검색 속도가 느려집니다. (세 번째로 메모리가 아닌 디스크를 읽는 경우 해시 버킷은 연속적 일 가능성이 높고 바이너리 트리는 로컬이 아닌 액세스를 거의 보장합니다.)
일반적으로 빠르게하려면 해시를 사용하십시오. 제한된 성능을 보장하려면 이진 트리를 사용할 수 있습니다.
놀랍게도, 보장 된 O (1)를 제공하는 Cuckoo 해싱에 대해 언급 한 사람은 아무도 없으며, 완벽한 해싱과 달리 할당 된 모든 메모리를 사용할 수 있습니다. 완벽한 해싱은 보장 된 O (1)으로 끝날 수 있지만 더 많은 부분을 낭비합니다. 배당. 경고? 모든 최적화가 삽입 단계에서 수행되기 때문에 삽입 시간은 특히 요소 수가 증가함에 따라 매우 느릴 수 있습니다.
나는 이것의 일부 버전이 ip 조회를 위해 라우터 하드웨어에서 사용된다고 생각합니다.
링크 텍스트 보기
Dictionary / Hashtable은 더 많은 메모리를 사용하고 배열에 비해 채우는 데 더 많은 시간이 걸립니다. 그러나 검색은 배열 내에서 이진 검색이 아닌 사전에 의해 수행됩니다.
다음은 1000 만 개의 Int64 항목을 검색하고 채울 수있는 숫자입니다 . 또한 직접 실행할 수있는 샘플 코드도 있습니다.
사전 메모리 : 462,836
어레이 메모리 : 88,376
사전 채우기 : 402
어레이 채우기 : 23
사전 검색 : 176
검색 어레이 : 680
using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace BinaryVsDictionary
{
internal class Program
{
private const long Capacity = 10000000;
private static readonly Dictionary<long, long> Dict = new Dictionary<long, long>(Int16.MaxValue);
private static readonly long[] Arr = new long[Capacity];
private static void Main(string[] args)
{
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
Dict.Add(i, i);
}
stopwatch.Stop();
Console.WriteLine("Populate Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
Arr[i] = i;
}
stopwatch.Stop();
Console.WriteLine("Populate Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
long value = Dict[i];
// Console.WriteLine(value + " : " + RandomNumbers[i]);
}
stopwatch.Stop();
Console.WriteLine("Search Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
long value = BinarySearch(Arr, 0, Capacity, i);
// Console.WriteLine(value + " : " + RandomNumbers[i]);
}
stopwatch.Stop();
Console.WriteLine("Search Array: " + stopwatch.ElapsedMilliseconds);
Console.ReadLine();
}
private static long BinarySearch(long[] arr, long low, long hi, long value)
{
while (low <= hi)
{
long median = low + ((hi - low) >> 1);
if (arr[median] == value)
{
return median;
}
if (arr[median] < value)
{
low = median + 1;
}
else
{
hi = median - 1;
}
}
return ~low;
}
}
}
나는 크기가 ~ 1M 인 문제 세트에서 해싱이 더 빠를 것이라고 강력하게 의심합니다.
숫자에 대해서만 :
이진 검색에는 ~ 20 개의 비교가 필요합니다 (2 ^ 20 == 1M)
해시 조회에는 검색 키에 대해 1 개의 해시 계산이 필요하며, 가능한 충돌을 해결하기 위해 나중에 몇 번의 비교가 필요할 수 있습니다.
편집 : 숫자 :
for (int i = 0; i < 1000 * 1000; i++) {
c.GetHashCode();
}
for (int i = 0; i < 1000 * 1000; i++) {
for (int j = 0; j < 20; j++)
c.CompareTo(d);
}
시간 : c = "abcde", d = "rwerij"해시 코드 : 0.0012 초. 비교 : 2.4 초.
disclaimer: Actually benchmarking a hash lookup versus a binary lookup might be better than this not-entirely-relevant test. I'm not even sure if GetHashCode gets memoized under-the-hood
I'd say it depends mainly on the performance of the hash and compare methods. For example, when using string keys that are very long but random, a compare will always yield a very quick result, but a default hash function will process the entire string.
But in most cases the hash map should be faster.
I wonder why no one mentioned perfect hashing.
It's only relevant if your dataset is fixed for a long time, but what it does it analyze the data and construct a perfect hash function that ensures no collisions.
Pretty neat, if your data set is constant and the time to calculate the function is small compared to the application run time.
It depends on how you handle duplicates for hash tables (if at all). If you do want to allow hash key duplicates (no hash function is perfect), It remains O(1) for primary key lookup but search behind for the "right" value may be costly. Answer is then, theorically most of the time, hashes are faster. YMMV depending on which data you put there...
Here it's described how hashes are built and because the Universe of keys is reasonably big and hash functions are built to be "very injective" so that collisions rarely happen the access time for a hash table is not O(1) actually ... it's something based on some probabilities. But,it is reasonable to say that the access time of a hash is almost always less than the time O(log_2(n))
Of course, hash is fastest for such a big dataset.
One way to speed it up even more, since the data seldom changes, is to programmatically generate ad-hoc code to do the first layer of search as a giant switch statement (if your compiler can handle it), and then branch off to search the resulting bucket.
The answer depends. Lets think that the number of elements 'n' is very large. If you are good at writing a better hash function which lesser collisions, then hashing is the best. Note that The hash function is being executed only once at searching and it directs to the corresponding bucket. So it is not a big overhead if n is high.
Problem in Hashtable: But the problem in hash tables is if the hash function is not good (more collisions happens), then the searching isn't O(1). It tends to O(n) because searching in a bucket is a linear search. Can be worst than a binary tree. problem in binary tree: In binary tree, if the tree isn't balanced, it also tends to O(n). For example if you inserted 1,2,3,4,5 to a binary tree that would be more likely a list. So, If you can see a good hashing methodology, use a hashtable If not, you better using a binary tree.
This is more a comment to Bill's answer because his answer have so many upvotes even though its wrong. So I had to post this.
I see lots of discussion about what is the worst case complexity of a lookup in hashtable, and what is considered amortized analysis / what is not. Please check the link below
Hash table runtime complexity (insert, search and delete)
worst case complexity is O(n) and not O(1) as opposed to what Bill says. And thus his O(1) complexity is not amortized since this analysis can only be used for worst cases (also his own wikipedia link says so)
https://en.wikipedia.org/wiki/Hash_table
https://en.wikipedia.org/wiki/Amortized_analysis
이 질문은 순수한 알고리즘 성능의 범위보다 더 복잡합니다. 바이너리 검색 알고리즘이 캐시 친화적이라는 요소를 제거하면 일반적으로 해시 조회가 더 빨라집니다. 알아내는 가장 좋은 방법은 프로그램을 빌드하고 컴파일러 최적화 옵션을 비활성화하는 것입니다. 일반적으로 알고리즘 시간 효율성이 O (1) 인 경우 해시 조회가 더 빠르다는 것을 알 수 있습니다.
그러나 컴파일러 최적화를 활성화하고 10,000 개 미만의 샘플 개수로 동일한 테스트를 시도하면 이진 검색은 캐시 친화적 인 데이터 구조의 이점을 활용하여 해시 조회보다 성능이 뛰어납니다.
참고 URL : https://stackoverflow.com/questions/360040/which-is-faster-hash-lookup-or-binary-search
'IT TIP' 카테고리의 다른 글
| Vagrant / VirtualBox / Apache2 이상한 캐시 동작 (0) | 2020.11.19 |
|---|---|
| 꿀꺽 꿀꺽에서 카르마 작업 실행 문제 (0) | 2020.11.19 |
| mysql 서버 포트 번호 (0) | 2020.11.19 |
| Java에서 main 메소드를 오버로드 할 수 있습니까? (0) | 2020.11.19 |
| 정확한 시간에 실행되도록 크론 작업을 설정하는 방법은 무엇입니까? (0) | 2020.11.19 |