Как я должен сопоставить строковые ключи со значениями в Java эффективным способом памяти?

Question

Я ищу способ сохранить отображение строки-> int.HashMap, конечно, является наиболее очевидным решением, но, поскольку я ограничен в памяти и мне нужно хранить 2 миллиона пар, ключи длиной 7 символов, мне нужно что-то, что эффективно использует память, скорость поиска является второстепенным параметром.

В настоящее время я иду по линии:

List<Tuple<String, int>> list = new ArrayList<Tuple<String, int>>();
list.add(...); // load from file
Collections.sort(list);

и затем для поиска:

Collections.binarySearch(list, key); // log(n), acceptable

Должен ли я пойти на собственное дерево (каждый узел один символ, каждый лист с результатом), или существует ли уже существующая коллекция, которая хорошо подходит для этого?Строки являются практически последовательными (британские почтовые индексы, они не сильно отличаются), поэтому я ожидаю здесь хорошей экономии памяти.

Answer 1

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

Answer 2

Проблема заключается в нехватке памяти объектов, но используя некоторые приемы, вы можете попытаться реализовать свой собственный хэш-набор. Что-то вроде это . Как и другие говорили, у строк довольно большие накладные расходы, поэтому вам нужно как-то их «сжать». Также старайтесь не использовать слишком много массивов (списков) в хеш-таблице (если вы используете цепочку типа хеш-таблицы), так как они также являются объектами и также имеют накладные расходы. Еще лучше сделать открытую хэш-таблицу адресации.

Answer 3

Поскольку вы собираетесь использовать хеширование, вы можете попробовать числовые преобразования строк на основе значений ASCII.самой простой идеей будет

    int sum=0;
    for(int i=0;i<arr.length;i++){
        sum+=(int)arr[i];

    }

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

    public int hasher(int sum){
       return sum%(a prime number);
    }

, выбор простого числа, которое не близко к точной степени двух, улучшает характеристики и дает лучшее равномерное хешированное распределение ключей.

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

Например: если вы используете вышеупомянутый метод, и "abc", и "cab" будут хэшированы в одном месте.но если вам нужно, чтобы они хранились в двух разных местах, укажите веса для таких мест, как мы используем системы счисления.

     int sum=0;
     int weight=1;
     for(int i=0;i<arr.length;i++){
         sum+= (int)arr[i]*weight;
         weight=weight*2; // using powers of 2 gives better results. (you know why :))
     }  

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

Answer 4

На самом деле HashMap и List являются слишком общими для такой конкретной задачи, как поиск int по почтовому индексу. Вы должны использовать преимущество знания, какие данные используются. Одним из вариантов является использование дерева префиксов с листьями, в которых хранится значение int. Кроме того, это может быть сокращено, если (мое предположение) много кодов с одинаковыми префиксами отображаются в одно и то же целое число.

Поиск int по почтовому индексу будет линейным в таком дереве и не будет расти при увеличении количества кодов, сравните с O (log (N)) в случае двоичного поиска.

Answer 5

попробуйте это

OptimizedHashMap<String, int[]> myMap = new OptimizedHashMap<String, int[]>();
for(int i = 0; i < 2000000; i++)
{
  myMap.put("iiiiii" + i, new int[]{i});
}
System.out.println(myMap.containsValue(new int[]{3}));
System.out.println(myMap.get("iiiiii" + 1));

---

public class OptimizedHashMap<K,V> extends HashMap<K,V>
{
    public boolean containsValue(Object value) {
    if(value != null)
    {
        Class<? extends Object> aClass = value.getClass();
        if(aClass.isArray())
        {
            Collection values = this.values();
            for(Object val : values)
            {
                int[] newval = (int[]) val;
                int[] newvalue = (int[]) value;
                if(newval[0] == newvalue[0])
                {
                    return true;
                }
            }
        }
    }
    return false;
}

Answer 6

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

public class MyKey implements Comparable<MyKey>
{
    char[7] keyValue;

    public MyKey(String keyValue)
    {
        ... load this.keyValue from the String keyValue.
    }

    public int compareTo(MyKey rhs)
    {
        ... blah
    }

    public boolean equals(Object rhs)
    {
        ... blah
    }

    public int hashCode()
    {
        ... blah
    }
}