В чем разница между LinkedHashSet и HashSet?

Разница между LinkedHashSet и HashSet

Оба класса - это реализации интерфейса Set в Java, но с важными отличиями в способе хранения элементов.

Основное отличие: Порядок элементов

HashSet:

• Хранит элементы в произвольном порядке
• Порядок может меняться при добавлении/удалении
• Базируется на хеш-таблице

LinkedHashSet:

• Сохраняет порядок вставки элементов
• Базируется на комбинации хеш-таблицы и двусвязного списка (LinkedList)
• Порядок предсказуем

Демонстрация

import java.util.*;

public class SetExample {
    public static void main(String[] args) {
        // HashSet - произвольный порядок
        Set<String> hashSet = new HashSet<>();
        hashSet.add("Java");
        hashSet.add("Python");
        hashSet.add("JavaScript");
        hashSet.add("Go");
        
        System.out.println("HashSet: " + hashSet);
        // Вывод может быть: [Java, Go, Python, JavaScript]
        // или [JavaScript, Python, Java, Go]
        // или любой другой порядок
        
        // LinkedHashSet - порядок вставки
        Set<String> linkedSet = new LinkedHashSet<>();
        linkedSet.add("Java");
        linkedSet.add("Python");
        linkedSet.add("JavaScript");
        linkedSet.add("Go");
        
        System.out.println("LinkedHashSet: " + linkedSet);
        // Всегда выведет: [Java, Python, JavaScript, Go]
        // Ровно в том порядке, в котором добавили
    }
}

Вывод:

HashSet: [Go, Java, Python, JavaScript]
LinkedHashSet: [Java, Python, JavaScript, Go]

Внутренняя структура

HashSet - только хеш-таблица:

┌─────────────────────────────────┐
│   HashMap<K, Object>            │
├─────────────────────────────────┤
│ Index │ Key │ Value             │
├─────────────────────────────────┤
│  0    │ Java   │ PRESENT        │
│  3    │ Python │ PRESENT        │
│  5    │ Go     │ PRESENT        │
│  7    │ JavaScript │ PRESENT    │
└─────────────────────────────────┘

LinkedHashSet - хеш-таблица + двусвязный список:

┌─────────────────────────────────────────────┐
│   LinkedHashMap<K, V>                       │
├─────────────────────────────────────────────┤
│ HashMap часть (для быстрого поиска)         │
│ + LinkedList часть (для порядка)            │
├─────────────────────────────────────────────┤

Порядок (двусвязный список):
Java ←→ Python ←→ JavaScript ←→ Go

Производительность

Операции (в среднем O(1)):

Set<Integer> hashSet = new HashSet<>();
Set<Integer> linkedSet = new LinkedHashSet<>();

// add() - O(1) в обоих
hashSet.add(100);
linkedSet.add(100);

// remove() - O(1) в обоих
hashSet.remove(100);
linkedSet.remove(100);

// contains() - O(1) в обоих
hashSet.contains(100);
linkedSet.contains(100);

// iteration - O(n)
for (Integer i : hashSet) {          // случайный порядок
    System.out.println(i);
}

for (Integer i : linkedSet) {        // порядок вставки
    System.out.println(i);
}

LinkedHashSet немного медленнее из-за работы двусвязного списка, но разница минимальна (примерно 10-15% медленнее).

Потребление памяти

LinkedHashSet потребляет больше памяти из-за дополнительных ссылок (next/prev) для каждого элемента:

HashSet: 40 байт на элемент (приблизительно)
LinkedHashSet: 56 байт на элемент (приблизительно)

Для 1 000 000 элементов:
HashSet: ~40 МБ
LinkedHashSet: ~56 МБ

Когда использовать

HashSet - когда:

• Порядок элементов не важен
• Нужна максимальная производительность
• Нужно сэкономить память

// Пример: проверка наличия тега
Set<String> tags = new HashSet<>(Arrays.asList("java", "python", "go"));
if (tags.contains("java")) {
    System.out.println("Found!");
}

LinkedHashSet - когда:

• Нужно сохранить порядок вставки
• Нужно повторять элементы в определённом порядке
• Нужна предсказуемость

// Пример: история действий пользователя
Set<String> userActions = new LinkedHashSet<>();
userActions.add("login");
userActions.add("view_profile");
userActions.add("edit_settings");
userActions.add("logout");

for (String action : userActions) {
    System.out.println(action);  // Всегда в порядке вставки
}
// login → view_profile → edit_settings → logout

Практические примеры

Пример 1: Удаление дубликатов с сохранением порядка

List<String> list = Arrays.asList("apple", "banana", "apple", "cherry", "banana");

// С HashSet - теряется порядок
Set<String> hashSet = new HashSet<>(list);
System.out.println(hashSet);  // [cherry, apple, banana] или другой порядок

// С LinkedHashSet - сохраняется порядок
Set<String> linkedSet = new LinkedHashSet<>(list);
System.out.println(linkedSet);  // [apple, banana, cherry]

Пример 2: Кеш с известным порядком

public class UserCache {
    // Кеш недавно посещённых пользователей в порядке посещения
    private Set<String> recentUsers = new LinkedHashSet<>();
    
    public void addUser(String userId) {
        recentUsers.remove(userId);  // Удалить если есть
        recentUsers.add(userId);     // Добавить в конец
        
        if (recentUsers.size() > 10) {
            // Удалить самого старого
            recentUsers.remove(recentUsers.iterator().next());
        }
    }
    
    public List<String> getRecentUsers() {
        return new ArrayList<>(recentUsers);
        // Вернёт в порядке посещения
    }
}

Пример 3: LRU Cache

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);  // accessOrder = true
        this.capacity = capacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

// Использование
LRUCache<String, String> cache = new LRUCache<>(3);
cache.put("a", "1");
cache.put("b", "2");
cache.put("c", "3");
cache.get("a");  // "a" становится самым свежим
cache.put("d", "4");  // "b" удаляется (самый старый)

Ещё одна реализация: TreeSet

Есть и третья реализация Set - TreeSet, которая сортирует элементы:

Set<Integer> treeSet = new TreeSet<>();
treeSet.add(3);
treeSet.add(1);
treeSet.add(2);

System.out.println(treeSet);  // [1, 2, 3] - ОТСОРТИРОВАНО

// Но медленнее - O(log n) для add/remove/contains

Сравнительная таблица

┌─────────────────┬──────────────┬─────────────┬─────────────┬──────────────┐
│ Операция        │ HashSet      │ LinkedHashSet│ TreeSet     │ CopyOnWrite  │
├─────────────────┼──────────────┼─────────────┼─────────────┼──────────────┤
│ add()           │ O(1)         │ O(1)        │ O(log n)    │ O(n)         │
│ remove()        │ O(1)         │ O(1)        │ O(log n)    │ O(n)         │
│ contains()      │ O(1)         │ O(1)        │ O(log n)    │ O(n)         │
│ Порядок         │ Случайный    │ Вставки     │ Сортировка  │ Вставки      │
│ Память          │ Минимум      │ +список     │ Средняя     │ Максимум     │
│ Параллелизм     │ Нет          │ Нет         │ Нет         │ Да           │
└─────────────────┴──────────────┴─────────────┴─────────────┴──────────────┘

Вывод

HashSet - универсальный выбор, когда порядок не важен. LinkedHashSet - выбор, когда нужен предсказуемый порядок вставки. TreeSet - выбор, когда нужна сортировка.

Все три работают как Set (без дубликатов), но по-разному организуют внутренние данные.