Как хэшировать диапазон чисел в одну позицию в хеш-таблице - PullRequest
Новая
       42

Как хэшировать диапазон чисел в одну позицию в хеш-таблице

9 голосов
/ 11 декабря 2011

В основном у меня есть массив 2xN от целых до целых, который указывает, от какой позиции до какой позиции местоположения объектов.Затем у меня есть второй массив целых, и я хочу найти, какие целые и какие объекты.Например:

Первый массив

A: 0 - 500

B: 501 - 900

C: 901 - 1055

D: 1056 - 9955 и т. Д.

Второй массив: 1, 999, 3, 898, 55, 43, 1055, 593, 525, 3099 и т. Д.

Это должно вернуть A, C, A, B, A, A, C, B, B, D и т. Д.

Я пытаюсь выяснить, есть ли способ хеширования первого массива с использованием некоторых хеш-функцийтак, что при хешировании второго массива я получу столкновение, если оно попадает в диапазон объекта.Любые идеи, как это сделать или если это возможно?

Спасибо!

Ответы [ 5 ]

3 голосов
/ 16 января 2017

Вы можете использовать NavigableMap.

Пример кода: 

NavigableMap<Integer, String> map = new TreeMap<Integer, String>();
map.put(0, "A");
map.put(501, "B");
map.put(901, "C");
map.put(1056, "D");

System.out.println(map.floorEntry(1).getValue());
System.out.println(map.floorEntry(999).getValue());
System.out.println(map.floorEntry(3).getValue());
System.out.println(map.floorEntry(898).getValue());

Выход:

A С B

3 голосов
/ 12 января 2012

Вы можете использовать некоторую структуру данных, например, дерево интервалов, для хранения первого массива.

http://en.wikipedia.org/wiki/Interval_tree

Затем, когда вы проходите второй массив, вы можете просто запросить у дерева соответствующий интервал. Таким образом, вам потребуется O (log n) времени для запроса каждого элемента второго массива.

1 голос
/ 06 марта 2013

Для любого, кто натыкается на эту страницу, я нашел этот похожий вопрос.

0 голосов
/ 14 декабря 2011

Ваша проблема тесно связана с декодированием BWT.

Если я правильно понимаю вашу проблему, вы получите первый массив в виде потока.

Тогда, если у вас есть второй массив в памяти, вам просто нужно создать его «обратный массив». Так что, например:

Второй массив: 1, 9, 3, 8, 5, 4, 2, 6, 7

Становится

Обратный второй массив: 1, 7, 3, 6, 5, 8, 9, 4, 2

Итак, теперь, получив ваш поток, вы сразу знаете, где разместить каждого персонажа.

0 голосов
/ 11 декабря 2011

Вы не можете использовать хеширование, но вы можете отсортировать конечные точки интервала и выполнить поиск пополам.

Примерно так (в python, но, надеюсь, это имеет смысл для вас): 

endpoints = [501, 901, 1056, 9956]
for x in [1, 999, 898, 55, 43, 1055, 593, 525, 3099]:
    print x, 'ABCD'[bisect.bisect_left(endpoints, x)]
...