Map algorithm in java

Содержание

Java Map with keys of 3 columns
9 Answers 9
Подробный разбор класса HashMap

Java Map with keys of 3 columns

I need a map in which my key should be based on 3 columns, say C1, C2, C3 . C1 has highest priority. C2 has one less than C1 and C3 has one less than C2 . How do i create key in the map such that if somebody asks for information on C1 , I should able to give all the values which has C1 . I also should be able to return all the values if asked for C1 & C2

This is not a standard problem. Lets approach this problem specific to current scenario for your usage. Can you please tell what is the data type of C1,C2 and C3 ? If they are integers then what would be the range of them?

9 Answers 9

You can use the same strategy as multicolumn indexes in databases, if your key columns can be ordered (i.e., in Java, they need to be Comparable ) and can easily define maximum and minimum values for all but the first.

An example with integer columns:

public class Key implements Comparable  < int c1, c2, c3; private static final int c2_min = Integer.MIN_VALUE; private static final int c2_max = Integer.MAX_VALUE; private static final int c3_min = Integer.MIN_VALUE; private static final int c3_max = Integer.MAX_VALUE; @Override public int compareTo(Key o) < if (c1!=o.c1) return Integer.compare(c1, o.c1); if (c2!=o.c2) return Integer.compare(c2, o.c2); return Integer.compare(c3, o.c3); >// constructor, equals, . >

and then you can get all entries for some value k1 in c1 like this:

map.subMap(new Key(k1, Key.c2_min, 0), new Key(k1, Key.c2_max, 0));

Likewise, using the first two columns:

map.subMap(new Key(k1, k2, Key.c3_min), new Key(k1, k2, Key.c3_max));

Assuming a byte comparator, you can use MIN = new byte[0] . For MAX , if you have a maximum array size, just use it and initialize all elements with Byte.MAX_VALUE . Otherwise, you have to choose some instance (defined as static final ) and explicitly check for it in compareTo with == . Finally, depending on your application, null might also work as a maximum value by considering it explicitly in compareTo .

One Map and one Map and one Map.

You can wrap the three maps into a class and implement you method.

By «priority», I presume you mean what is usually referred to as primary, secondary and tertiary keys.

If they’re all string fields, concatenate them into a single string and use that as the key. In your case, the key is C1+C2+C3 (where «+» refers to string concatenation).

A Map will always return just one value for a key. You can’t have it return multiple values based on your key classes content.

The simple way is to keep a separate map for each key type and return the appropriate results based on the passed key.

A three-level index where a higher-level key can be used to access all lower level keys and objects will require a three-level map.

class ThreeLevelMap < private Map>> store = new HashMap>>(); . public V put(K1 key1, K2 key2, K3 key3, V value) < . >public V get(K1 key1, K2 key2, K3 key3) < . >public static class TLMEntry  < . >public Collection get(K1 key1, K2 key2) < . >public Collection get(K1 key1) < . >>

This is a basic skeleton but should get you going in the right direction.

This seems more like a database problem. If you had a database with a table structured like:

CREATE TABLE MyMap ( id IDENTITY PRIMARY KEY, c1 int, -- Change data types as needed. c2 int, c3 int, v int);

then you would simply issue SELECT statements against it. You might want to use any of the in-memory Java databases.

If you don’t want to do that, you could do the equivalent purely in Java functionally by writing a container class value class:

class Cdata < private int c1; private int c2; private int c3; private int v; // Constructors and getters elided. public boolean match(int c1) < return this.c1 == c1; >public boolean match(int c1, int c2) < return match(c1) && this.c2 == c2; >public boolean match(int c1, int c2, int c3) < return match(c1, c2) && this.c3 == c3; >>

Then create a List and use a functional programming library with filter methods. Or, wait for Java 8 lambdas. Using a Map>>> is too confusing.

You can use TreeMap to acheive your usecase. I am assuming the following: Your three columns map to 3 increasing integer values i.e

where C1 = 1 is the highest priority and C2 = 2 is next in line and so on.

Note: Your keys need not always be Integers, you can use any type if you provide the proper Comparator to your TreeMap .

With this in place, you could do something like:

TreeMap treeMap = new TreeMap(); treeMap.put(1, "One"); treeMap.put(2, "two"); treeMap.put(3, "three"); List list = getMappedValues(treeMap, 1);// returns One, Two, Three //List list = getMappedValues(treeMap, 2);// returns Two, Three //List list = getMappedValues(treeMap, 3);// returns Three //List list = getMappedValues(treeMap, 4);// returns null if(list != null) < //do something with the list of values >private static List getMappedValues(TreeMap map, Integer key) < Entrye = map.ceilingEntry(key); if(e == null) < return null; >List list = new ArrayList(); while(e != null) < list.add(e.getValue()); key = e.getKey(); e = map.higherEntry(key); >return list; >

Источник

Подробный разбор класса HashMap

Прежде чем переходить к подробному рассмотрению класса, остановимся на базовых понятиях, связанных с хеш-таблицами. В данной статье не будут рассматриваться методы для работы с хеш-отображением. Наглядно и подробно будут рассмотрены только операции вставки, поиска и удаления. Прочитать описание имеющихся у HashMap методов, я думаю не составит труда у того же Шилдта. Возможно, в будущем я напишу ещё одну статью, посвященную таким методам, но пока это под вопросом. По сравнению с Java 7 класс HashMap в Java 8 претерпел значительные изменения (+1000 строк кода). Про реализацию в Java 7 можно почитать тут (но уже не акутально): хабр Хеш-таблицей называется структура данных, реализующая интерфейс ассоциативного массива (абстрактная модель «ключ – значение» или entry), которая обеспечивает очень быструю вставку и поиск: независимо от количества элементов вставка и поиск (а иногда и удаление) выполняются за время, близкое к константе – O(1). По сути, это обычный массив, где местоположение элемента зависит от значения самого элемента. Связь между значением элемента и его позицией в хеш-таблице задает хеш-функция. Хеш-функция получает входную часть данных, которую мы называем ключом, а на выходе она выдает целое число, известное как хеш-значение (или хеш-код). Затем, хеш-значение привязывает наш ключ к определенному индексу хеш-таблицы. Для основных операций: вставки, поиска и удаления мы используем одну и ту же хеш-функцию, поэтому эти операции осуществляются довольно быстро. По этой причине важно, чтобы хеш-функция вела себя последовательно и выводила один и тот же индекс для одинаковых входных данных. Стоит отметить, что полученный хеш-код может быть огромным числовым значением, а исходный массив условно рассчитан только на 16 элементов. Не создавать же массив на миллиард элементов, чтобы добавить туда всего десять? Поэтому мы этот хеш-код должны как-то трансформировать в значения от 0 до 15 (если размер массива 16). И вот для этого используются дополнительные преобразования. Таким образом, мы генерируем индекс для минимизации размера массива. Например, в HashMap до Java 8 использовался вот такой дополнительный метод для нахождения нужной ячейки:

 static int indexFor(int h, int length)

На вход он принимал хеш-код полученный в результате работы hashCode() и длину внутреннего массива (количество ячеек). А возвращал результат «хеш-код» –> побитовое «И» –> (длина массива – 1). Класс HashMap наследуется от класса AbstractMap и реализует следующие интерфейсы: Map , Cloneable , Serializable . За хеш-функцию в Java отвечает метод hashCode() . Реализация по умолчанию hashCode() возвращает значение, которое называется идентификационный хеш (identity hash code). Даже если класс переопределяет hashCode() , вы всегда можете получить идентификационный хеш объекта с помощью вызова System.identityHashCode(Object o) . Реализация по умолчанию hashCode() в OpenJDK не имеет ничего общего с адресом памяти, как это порой принято считать. Подробнее здесь: хабр В HashMap хеш-таблица реализована на основе массива (а если точнее — динамического, так как таблица может расширяться) односвязных списков. По сути, мы получаем хеш-код ключа в результате работы метода hashCode() , который затем модифицируется (как рассмотрим далее), а внутри с помощью дополнительного метода полученные значения распределяются по нужным ячейкам. Элементы массива (ячейки) еще называются корзинами «buckets», которые используются для хранения отдельно взятых узлов. Каждый из бакетов представляет из себя коллекцию (список или дерево). Узел представляет собой объект вложенного класса Node (или TreeNode при древовидной структуре). По сути, внутри ячейки массива лежит LinkedList , только список односвязный, либо красное-черное дерево, которое лежит в основе реализации другого класса — TreeMap .

Вариант с красно-черным деревом возникает не столь часто (как, что и куда — далее), да и структура эта довольно непростая для понимания, поэтому акцент будет сделан на узле типа Node. Node — это вложенный класс внутри HashMap , который имеет следующие поля:

final int hash — хеш текущего элемента, который мы получаем в результате хеширования ключа;
final K key — ключ текущего элемента. Именно сюда записывается то, что вы указываете первым объектом в методе put() ;
V value — значение текущего элемента. А сюда записывается то, что вы указываете вторым объектом в методе put() ;
Node < K, V>next — ссылка на следующий узел в пределах одной корзины. Список же связный, поэтому ему нужна ссылка не следующий узел, если такой имеется.

transient Node < K, V>[] table – сама хеш-таблица, реализованная на основе массива, для хранения пар «ключ-значение» в виде узлов. Здесь хранятся наши Node;
transient int size — количество пар «ключ-значение»;
int threshold — предельное количество элементов, при достижении которого размер хэш-таблицы увеличивается вдвое. Рассчитывается по формуле (capacity * loadFactor);
final float loadFactor — этот параметр отвечает за то, при какой степени загруженности текущей хеш-таблицы необходимо создавать новую хеш-таблицу, т.е. как только хеш-таблица заполнилась на 75%, будет создана новая хеш-таблица с перемещением в неё текущих элементов (затратная операция, так как требуется перехеширование всех элементов);
transient Set< Map.Entry< K,V>> entrySet — содержит кешированный entrySet() , с помощью которого мы можем перебирать HashMap .

static final int DEFAULT_INITIAL_CAPACITY= 1
static final int MAXIMUM_CAPACITY = 1
static final float DEFAULT_LOAD_FACTOR = 0.75f — коэффициент загрузки, используемый по умолчанию;
static final int TREEIFY_THRESHOLD = 8 — это «порог» количества элементов в одной корзине, при достижении которого внутренний связный список будет преобразован в древовидную структуру (красно-черное дерево).
static final int UNTREEIFY_THRESHOLD = 6 — если количество элементов в одной корзине уменьшится до 6, то произойдет обратный переход от дерева к связному списку;
static final int MIN_TREEIFY_CAPACITY = 64 — минимальная емкость (количество корзин) хеш-таблицы, при которой возможен переход к древовидной структуре. Т.е. если в хеш-таблице по крайней мере 64 бакета и в одном бакете 8 или более элементов, то произойдет переход к древовидной структуре.

public HashMap() — создает хеш-отображение по умолчанию: объемом (capacity) = 16 и с коэффициентом загруженности (load factor) = 0.75 ;
public HashMap(Map < ? extends K, ? extends V>m) — создает хеш-отображение, инициализируемое элементами другого заданного отображения с той начальной емкостью, которой хватит вместить в себя элементы другого отображения;
public HashMap(int initialCapacity) — создает хеш-отображение с заданной начальной емкостью. Для корректной и правильной работы HashMap размер внутреннего массива обязательно должен быть степенью двойки (т.е. 16, 64, 128 и т.д.);
public HashMap(int initialCapacity, float loadFactor) — создает хеш-отображение с заданными параметрами: начальной емкостью и коэффициентом загруженности.

 static final int hash(Object key) < int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); >

 System.out.println("KING".hashCode());

 if ((tab = table) == null || (n = tab.length) == 0)

Источник