Поиск повторяющегося алгоритма - Java

Question

У меня есть набор значений, массив, и я должен найти дубликаты ключей.Один из подходов - использовать 2 цикла.и итерация по списку для каждого значения, перезапускающего O (n2).

другая вещь, которую я могу сделать, это поместить значения в качестве ключей в HashTable.Я полагал, что hashtable вызовет исключение, если в нем уже есть такой же ключ.Но это не исключение

    Hashtable<String, String> ht = new Hashtable<String, String>();

    for (int i = 0; i<20; i++){
        ht.put(String.valueOf(i%10), String.valueOf(i%10));
    }

я правильно понимаю?Разве hastable / hashmap не генерирует исключение, если в нем уже есть такой же ключ?

Answer 1

Мое предложение: вы хотите HashSet вместо Hashtable:

Set<String> ht = new HashSet<String>();

for (int i = 0; i<20; i++){
    if ( !ht.add(String.valueOf(i%10)) ) {
       //it already existed, throw an exception or whatever
    }
}

Если вас не интересуют значения , которые вы добавляете на карту, вам почти наверняка понадобится Set, а не Map / таблица.

Answer 2

Нет, оно не выдает исключение, оно просто заменяет старое значение. Вы можете проверить, существует ли уже значение, вызвав get:

if (ht.get(key) != null) {
  // value already exists
}

Редактировать: Как предложил @Mark Peters, containsKey - более простое, а иногда и лучшее решение.

Answer 3

Согласно Java Docs, единственное исключение, которое может быть помещено, это NullPointerException, если ключ или значение равно нулю.Вы можете изменить свой цикл на что-то вроде:

for(int i = 0 ; i < 20 ; i++) {
    if (ht.containsKey(String.valueOf(i%10)))
        throw new Something();

    ht.put(String.valueOf(i%20), True);
}

Answer 4

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

Например, хэши ответят на вопрос "существует ли этот ключ?"быстро, что может помочь с вашим алгоритмом.

Answer 5

Вы можете увидеть в API документах , что put возвращает null, если в таблице ранее ничего не было для этого ключа, и предыдущее значение ключа, если оно было. (Это не вызывает исключения в любом случае.)

Answer 6

В зависимости от вашей памяти и ограничений времени выполнения, я бы порекомендовал что-то, если у вас ограничено пространство:

Вы можете отсортировать массив (наихудший случай O (nlog_n), если вы используете что-то вроде быстрой сортировки), а затем обойти его, чтобы найти дубликаты в соседних элементах.

Надеюсь, это поможет

Answer 7

Вот самый простой способ сделать это:

List yourList;
HashSet noDuplicates = new HashSet(yourList);
HashSet duplicates = new HashSet(yourList).removeAll(noDuplicates);

Answer 8

Из JavaDoc:

положить публичный объект положил (ключ объекта, Стоимость объекта) Сопоставляет указанный ключ с указанным значением в этой хеш-таблице. Ни ключ, ни значение не могут быть нулевыми. Значение можно получить, вызвав метод get с ключом, равным исходному ключу. Указано: положить в интерфейс карты Указано: положить в классе словарь Параметры: ключ - ключ хеш-таблицы значение - значение. Возвращает: предыдущее значение указанного ключа в этой хеш-таблице, или нуль, если у него его нет. Броски: NullPointerException - если ключ или значение являются нулем. Смотрите также: Object.equals (Object), get (Object)

Похоже, что это позволит вам перезаписать значение, но затем даст вам старое значение в качестве возвращаемого объекта.