Здравствуйте
Подскажите, пожалуйста, какие есть двусторонние hash таблицы т.е. где есть стандартно два объекта key и object, но можно получать не только объект object по key
но и key по object, только это должно быть open source и желательно реализованно не при помощи двух простых hash.
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте А>Подскажите, пожалуйста, какие есть двусторонние hash таблицы т.е. где есть стандартно два объекта key и object, но можно получать не только объект object по key А>но и key по object, только это должно быть open source и желательно реализованно не при помощи двух простых hash.
Боюсь таких нет, в силу определения хэш таблицы. Это можно организовать только используя 2 мэпы.
Для не хэш таблиц такое возможно, например строя индекс и по ключу и по значению. Но время поиска в них эквивалентно логарифму, а не константа как в случае хэш таблицы
Здравствуйте, Бизон, Вы писали:
Б>Но время поиска в них эквивалентно логарифму, а не константа как в случае хэш таблицы
Какое интересное заблуждение. Время поиска в хеш-таблице константа только когда все ключи после нормализации различны. Что на практике верно очень редко. Рекомендую освежить/обновить знания.
Здравствуйте, mikkri, Вы писали:
M>Здравствуйте, Бизон, Вы писали:
Б>>Но время поиска в них эквивалентно логарифму, а не константа как в случае хэш таблицы
M>Какое интересное заблуждение. Время поиска в хеш-таблице константа только когда все ключи после нормализации различны. Что на практике верно очень редко. Рекомендую освежить/обновить знания.
Гы гы
Для особо одаренных переформулируем так:
если n-количество ключей, p — максимальное количество различных нормализованных ключей
то время доступа эквивалентно n/p. Отношение n/p поддерживается в таблице постоянным с помощью операции rehash.
Уменьшение значения этой величины уменьшает время доступа но увеличивает потребление памяти. Увеличиние приводит к обратным последствиям.
Возвращаясь к моему утверждению про скорость доступа:
1) Если ключи после нормализации различны то скорость доступа равна 1
2) Если ключи не различны то средняя скорость доступа константа, размер константы n/p
Все рассуждения верны для хорошо распределенных ключей.
Здравствуйте, mikkri, Вы писали:
M>Здравствуйте, Бизон, Вы писали:
M>Б>Все рассуждения верны для хорошо распределенных ключей.
M>А где ж ты их возьмешь?
В каждой задаче свое распределение. Если ты сам генерируешь ключи то можешь судить об их распределении и имеет смысл использовать хэшмэп. Если же ты не знаешь как генерируются ключи, но хочешь иметь гарантированное время доступа, но не O(n), то имеет смысл использовать tree-map.
Здравствуйте, Бизон, Вы писали:
Б>В каждой задаче свое распределение. Если ты сам генерируешь ключи то можешь судить об их распределении и имеет смысл использовать хэшмэп. Если же ты не знаешь как генерируются ключи, но хочешь иметь гарантированное время доступа, но не O(n), то имеет смысл использовать tree-map.
tree-map не получится использовать если ключи не упорядочены (не Comparable).
Здравствуйте, Бизон, Вы писали:
Б>Здравствуйте, mikkri, Вы писали:
M>>Здравствуйте, Бизон, Вы писали:
M>>Б>Все рассуждения верны для хорошо распределенных ключей.
M>>А где ж ты их возьмешь? Б>В каждой задаче свое распределение. Если ты сам генерируешь ключи то можешь судить об их распределении и имеет смысл использовать хэшмэп. Если же ты не знаешь как генерируются ключи, но хочешь иметь гарантированное время доступа, но не O(n), то имеет смысл использовать tree-map.
Суждение здравое — нужно будет почаще об этом задумываться.
Но все же я не согласен с твоей категоричностью. Тем более что действительно, ключи могут быть несортируемыми.
Здравствуйте, C0s, Вы писали:
C0s>Здравствуйте, Blazkowicz, Вы писали:
B>>Периодически.
C0s>я, надо признаться, рассчитывал на пример из жизни, а не ответ типа "часто/не часто"
Один из самых очевидных примеров — обратная Map. Т.е. когда мы по объекту нужно вытащить ключь. Вещь экзотическая, но иногда нужна.
Еще ситуация когда ключ — составной. Т.е. ключем выступает JavaBean из нескольких полей. Конечно, можно ввести фиктивное упорядочивание, но, ИМХО, это только ухудшит код.
Здравствуйте, C0s, Вы писали:
C0s>я, надо признаться, рассчитывал на пример из жизни, а не ответ типа "часто/не часто"
например, составной ключ, одним из полей которого является boolean.
или я очень часто использую enumerations:
public class TestEnum {
public static final TestEnum VALUE1 = new TestEnum("VALUE1");
public static final TestEnum VALUE2 = new TestEnum("VALUE2");
public static final TestEnum VALUE3 = new TestEnum("VALUE3");
public static final TestEnum VALUE4 = new TestEnum("VALUE4");
public static final TestEnum VALUE5 = new TestEnum("VALUE5");
private final String myName; // for debug onlyprivate TestEnum(String name) {
myName = name;
}
public String toString() {
return myName;
}
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (!(o instanceof TestEnum)) {
return false;
}
final TestEnum testEnum = (TestEnum) o;
if (myName != null ? !myName.equals(testEnum.myName) : testEnum.myName != null) {
return false;
}
return true;
}
public int hashCode() {
return (myName != null ? myName.hashCode() : 0);
}
}
Здравствуйте, Lucker, Вы писали:
L>Здравствуйте, C0s, Вы писали:
C0s>>я, надо признаться, рассчитывал на пример из жизни, а не ответ типа "часто/не часто"
L>например, составной ключ, одним из полей которого является boolean. L>или я очень часто использую enumerations:
L>
L>public class TestEnum {
L> public static final TestEnum VALUE1 = new TestEnum("VALUE1");
L> public static final TestEnum VALUE2 = new TestEnum("VALUE2");
L> public static final TestEnum VALUE3 = new TestEnum("VALUE3");
L> public static final TestEnum VALUE4 = new TestEnum("VALUE4");
L> public static final TestEnum VALUE5 = new TestEnum("VALUE5");
L> private final String myName; // for debug only
L> private TestEnum(String name) {
L> myName = name;
L> }
L> public String toString() {
L> return myName;
L> }
L> public boolean equals(Object o) {
L> if (this == o) {
L> return true;
L> }
L> if (!(o instanceof TestEnum)) {
L> return false;
L> }
L> final TestEnum testEnum = (TestEnum) o;
L> if (myName != null ? !myName.equals(testEnum.myName) : testEnum.myName != null) {
L> return false;
L> }
L> return true;
L> }
L> public int hashCode() {
L> return (myName != null ? myName.hashCode() : 0);
L> }
L>}
L>
Почему не упорядочиваются? Добавь им поле index и упорядочивай по нему
L>так вот они тоже не упорядочиваются.
Здравствуйте, Бизон, Вы писали:
Б>Почему не упорядочиваются? Добавь им поле index и упорядочивай по нему
Ну это хак. В данном случае это семантически не упорядоченное множество. Меня интересует только равенство конкретному значению но никак не отношение больше/меньше. Метрика сравнения равна 0 при равенстве и не равна 0 при неравенстве.
Давай приведу более наглядный пример.
public class Attribute {
public static final Attribute FIRST_NAME = new Attribute("FIRST_NAME");
public static final Attribute SECOND_NAME = new Attribute("SECOND_NAME");
public static final Attribute AGE = new Attribute("AGE");
public static final Attribute SEX = new Attribute("SEX");
public static final Attribute BIRTHDAY = new Attribute("BIRTHDAY");
Здравствуйте, C0s, Вы писали:
C0s>я, надо признаться, рассчитывал на пример из жизни, а не ответ типа "часто/не часто"
Ну, вот что нашел в текущем проекте:
SWT. Проблемы с удалением TableEditor, автоматически они не всегда диспозятся. Надо хранить маппинг с ключем TableItem.
Pattern. Когда необходим в качестве ключа класс, чтобы определить, к примеру, обработчик бина.
Можно тут конечно задуматься над тем а не использовать ли имя класса. Но на первый взгляд улучшений от этого не видно.
GEF. Хранение Layout Constraints, в LayoutManager. Чтобы по визуальной части всегда можно было достать его Constraints. (Тут тоже можно сослаться на недоработку в архитектуре GEF, но всё же)
Здравствуйте, Lucker, Вы писали:
Б>>Почему не упорядочиваются? Добавь им поле index и упорядочивай по нему
L>Ну это хак. В данном случае это семантически не упорядоченное множество. Меня интересует только равенство конкретному значению но никак не отношение больше/меньше. Метрика сравнения равна 0 при равенстве и не равна 0 при неравенстве.
мне кажется, не стоит смешивать семантику (в этом случае семантика "работает" на уровне исходного текста программы) и математически обоснованные способы доступа к данным с гарантированной скоростью
я к тому, что практически всегда ключи можно сделать comparable (в крайнем случае с помощью wrapper'а, если изначальная реализация недоступна, а очень надо), в конкретном примере — просто потому что основываются на строках.
и этим свойством имеет смысл пользоваться там, где алгоритмы от этого будут выигрывать. другое дело, что правильнее в таких случаях пользоваться отдельным классом-компаратором, но это уже вопрос конечного дизайна
