HashMap Search for part of an key? [duplicate]
I am currently using HashMap
You have to iterate through all the HashMap, use getKey.length() and add or not (depending on the condition) to a List<>
Question: he is looking for entries that have 4 characters instead of 5 characters? Or he is looking for a series of 4 characters which may be within 5 characters?
8 Answers 8
Iterate is your only option unless you create a custom data structure:
If you need something more time efficient then you’d need an implementation of map where you are tracking these partial keys.
It seems like a use case for TreeMap rather than HashMap . The difference is that TreeMap preserves order. So you can find your partial match much quicker. You don’t have to go through the whole map.
You cannot do this via HashMap , you should write your own implementation for Map for implementing string length based searching in a map.
Unless ofcourse, he changes the requirements, uses the key with only the 4 characters, and stores the other data in an object in value. Another option is to use a custom Key Object, with custom hashCode() method.
I wouldn’t advise rolling one’s own Map<>. That’s probably overkill (and, besides, composition is often better than inheritance). However, I agree that the data structure, as-is, is not designed to do this.
You don’t need to implement all of Map. It is pretty easy to add extra stuff if you use the decorator pattern. So for example I want to log out every key added to a map? Fine, I make my LoggingMap implement Map and then you have to supply the actual instance of the Map it’s going to log out. That would work perfectly well in this case except instead of logging you’d keep track of the keys you want in a list or something along those lines.
Yes right Map implementation can be extension ( extends ) of HashMap or other exiting implementations, override only what is required. My point was for this question Map seems to be a right data-structure but with some modified get (for length based retrieval) and put (for optimal get say O(1) again). As all other answers shows external logic as a solution, having a specific Map would enforce encapsulating that logic inside map itself.
Map result = new HashMap; for(String key : yourMap.keySet()) < if(key.length() == 4)< result.put(key, yourMap.get(key); >> After executing this code you have all key/value pairs with 4 letter keys in result .
Set> s1 = map.entrySet(); for (Entry entry : s1) < if(entry.getKey().length == 4) //add it to a map; >First get the entry set to your hashmap. Iterate through the set and check the length of each key and add it to a map or use it as u want it.
With HashMap you can only go through keySet() and do contains() for String keys and your pattern.
As has been noted, there isn’t a terribly efficient* way to do it with the datastructure you have specified. However, if you add an additional Map> to keep track of the mapping from string length to the list of all keys with that length, then you will be able to do this very efficiently.
*Using just the Map, you would need to iterate through the entire capacity of the larger map, whereas adding this supplemental datastructure would impose an O(1) lookup (assuming you used a HashMap) followed by iteration through just the result set, which is the fastest possible outcome.
You can try this approach:
public Map filterMap(Map inputMap) < MapresultHashMap = new HashMap(); for (String key : inputMap.keySet()) < if(key.length()==5)< resultHashMap.put(key,inputMap.get(key)); >> return resultHashMap; > Структуры данных в картинках. HashMap
Продолжаю попытки визуализировать структуры данных в Java. В предыдущих сериях мы уже ознакомились с ArrayList и LinkedList, сегодня же рассмотрим HashMap.
HashMap — основан на хэш-таблицах, реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Данная реализация не дает гарантий относительно порядка элементов с течением времени. Разрешение коллизий осуществляется с помощью метода цепочек.
Создание объекта
- table — Массив типа Entry[], который является хранилищем ссылок на списки (цепочки) значений;
- loadFactor — Коэффициент загрузки. Значение по умолчанию 0.75 является хорошим компромиссом между временем доступа и объемом хранимых данных;
- threshold — Предельное количество элементов, при достижении которого, размер хэш-таблицы увеличивается вдвое. Рассчитывается по формуле (capacity * loadFactor);
- size — Количество элементов HashMap-а;
// Инициализация хранилища в конструкторе // capacity - по умолчанию имеет значение 16 table = new Entry[capacity]; 
Вы можете указать свои емкость и коэффициент загрузки, используя конструкторы HashMap(capacity) и HashMap(capacity, loadFactor). Максимальная емкость, которую вы сможете установить, равна половине максимального значения int (1073741824).
Добавление элементов
- Сначала ключ проверяется на равенство null. Если это проверка вернула true, будет вызван метод putForNullKey(value) (вариант с добавлением null-ключа рассмотрим чуть позже).
static int hash(int h) < h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); > Комментарий из исходников объясняет, каких результатов стоит ожидать — метод hash(key) гарантирует что полученные хэш-коды, будут иметь только ограниченное количество коллизий (примерно 8, при дефолтном значении коэффициента загрузки).
В моем случае, для ключа со значением »0» метод hashCode() вернул значение 48, в итоге:
h ^ (h >>> 20) ^ (h >>> 12) = 48 h ^ (h >>> 7) ^ (h >>> 4) = 51 static int indexFor(int h, int length)
При значении хэша 51 и размере таблице 16, мы получаем индекс в массиве:
if (e.hash == hash && (e.key == key || key.equals(e.key)))
void addEntry(int hash, K key, V value, int index) < Entrye = table[index]; table[index] = new Entry(hash, key, value, e); . > 
Для того чтобы продемонстрировать, как заполняется HashMap, добавим еще несколько элементов.
- Пропускается, ключ не равен null
h ^ (h >>> 20) ^ (h >>> 12) = 106054 h ^ (h >>> 7) ^ (h >>> 4) = 99486 
- Все элементы цепочки, привязанные к table[0], поочередно просматриваются в поисках элемента с ключом null. Если такой элемент в цепочке существует, его значение перезаписывается.
- Пропускается, ключ не равен null
h ^ (h >>> 20) ^ (h >>> 12) = 104100 h ^ (h >>> 7) ^ (h >>> 4) = 101603 // В table[3] уже хранится цепочка состоящая из элемента ["0", "zero"] Entry e = table[index]; // Новый элемент добавляется в начало цепочки table[index] = new Entry(hash, key, value, e); 
Resize и Transfer
Когда массив table[] заполняется до предельного значения, его размер увеличивается вдвое и происходит перераспределение элементов. Как вы сами можете убедиться, ничего сложного в методах resize(capacity) и transfer(newTable) нет.
void resize(int newCapacity) < if (table.length == MAXIMUM_CAPACITY) < threshold = Integer.MAX_VALUE; return; >Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); > Метод transfer() перебирает все элементы текущего хранилища, пересчитывает их индексы (с учетом нового размера) и перераспределяет элементы по новому массиву.
Если в исходный hashmap добавить, скажем, еще 15 элементов, то в результате размер будет увеличен и распределение элементов изменится.
Удаление элементов
У HashMap есть такая же «проблема» как и у ArrayList — при удалении элементов размер массива table[] не уменьшается. И если в ArrayList предусмотрен метод trimToSize(), то в HashMap таких методов нет (хотя, как сказал один мой коллега — «А может оно и не надо?«).
Небольшой тест, для демонстрации того что написано выше. Исходный объект занимает 496 байт. Добавим, например, 150 элементов.
Теперь удалим те же 150 элементов, и снова замерим.
Как видно, размер даже близко не вернулся к исходному. Если есть желание/потребность исправить ситуацию, можно, например, воспользоваться конструктором HashMap(Map).
hashmap = new HashMap(hashmap); Итераторы
HashMap имеет встроенные итераторы, такие, что вы можете получить список всех ключей keySet(), всех значений values() или же все пары ключ/значение entrySet(). Ниже представлены некоторые варианты для перебора элементов:
Инструменты для замеров — memory-measurer и Guava (Google Core Libraries).
java Get hashmap keys as integer array
Yes, integers are perfectly fine for being used as keys in a Map. It’s just that you will be putting an Integer instead of the primitive int in the Map but I don’t think that should be a problem for you. Also, auto-boxing will help you cut down the conversion from int to Integer call.
4 Answers 4
There is no direct way of converting a list of String s to a list of Integer s:
- Either you need to redefine your valueHashMap like this:
public HashMap valueHashMap = new HashMap(); . ArrayList intKeys = new ArrayList(valueHashMap.keySet()); ArrayList intKeys = new ArraList(); for (String stringKey : valueHashMap.keySet()) intKeys.add(Integer.parseInt(stringKey); public HashMap valueHashMap = new HashMap(); You can’t cast a List of one type to a List of another type, so you have to iterate through the keys and parse each one.
for(String k : valueHashMap.keySet())
@Joachim Sauer: That’s because my answer covered the general case (where you can sometimes cast) and my code was for this specific instance of the problem. Fixed it anyway to avoid confusion.
the problem is that many people call any kind of type conversion «casting» and that is wrong and confuses people even further.
You really have type problems. Why do you change the longs into Strings to store them in a map. Why not simply use Long, which needs less memory and is more descriptive. Then why use Integer.toString to transform a long into a String? By casting your long to an int, you risk loosing information by. Here’s how the code should probably look like:
private Map valueHashMap = new Hashmap(); long timeSinceEpoch = System.currentTimeMillis()/1000; valueHashMap.put(timeSinceEpoch, people_obj); List longKeys = new ArrayList(valueHashMap.keySet()); You can use org.apache.commons.collections.Transformer class for that as follows.
List intKeys = (List)CollectionUtils.collect(valueHashMap.keySet(), new Transformer() < @Override public Object transform(Object key) < return Integer.valueOf(key); >>, new ArrayList()); JSTL Access Integer/Long key in Hash Map
I am facing some problem in using EL in JSTL and not able to access Java Hash Map as I would like. I am aware that in EL the key, if Integer gets accessed as Long. I have following hash map definition that I am trying to access in JSTL —
In JSP page, I need to check if the map contains a specific key or not. I attempt to do that by checking if not empty as following —
Now the problem — If i define my map above as
In the above example, the second one is correctly accessing it as Long so I did not need to put «L» at the end of the element to access the map.
1 Answer 1
What is currObj ? Can you redefine its currVal member as a Long (or long )?
A numeric literal (matching the IntegerLiteral production in the EL syntax) will be represented as a Long . The expression currObj.currVal evaluates to an Integer . A Long never equals() an Integer , so one expression must result in a different type.
Essentially, what you need is an explicit type conversion. Nothing like this is built into EL, but you could create a custom EL function to do it for you. This is a static function that you implement in Java, then describe in a TLD. Another answer of mine gives an example of the packaging. Here’s what the function and its usage could look like in your case.
package com.y.taglib.core; public final class CoercionUtil < public static Long toLong(Long n) < return n; >> The TLD would look like this:
1.0 x-c http://dev.y.com/taglib/core/1.0 Coerce to a java.lang.Long. long long com.y.taglib.core.CoercionUtil java.lang.Long toLong(java.lang.Long) The JSP engine takes care of the necessary type coercion (from the Integer result of currVal to the Long required by the toLong() method. Your method is there simply to indicate the required type; without it, the JSP engine sees the (erased) type of the argument of testMap.get(Object) , and doesn’t see the need to perform any coercion since Integer is-an Object .