Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (778)
Games in Android Showcase (231)
games submitted by our members
Games in WIP (856)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Improving Map performance by knowing all keys up front?  (Read 5975 times)
0 Members and 1 Guest are viewing this topic.
Offline actual

JGO Coder

Medals: 25

« Posted 2012-12-16 02:33:19 »

I have run across a number of cases where I have a Map where once I set it up, the keys never change (although the values against them do). I don't necessarily know what the keys will be until I create the map but once I do they are fixed.

I was wondering, is there a way to take advantage of this fact to design a Map like data structure that retrieves values more efficiently than the standard implementations?

The class signature would roughly follow the Map interface and might look something like:

public class FixedKeyMap<K,V> {
   // Takes in a list of keys for the map.
   // These keys cannot be added to or removed from.
   // All values are initially set to null.
   public FixedKeyMap(List<K> keys) {}

   // If the Key is valid, replace its value with this one.
   // Otherwise do nothing or throw an exception.
   public void put(K key,V value) {}

   // If key is valid then get the value associated with it
   // Otherwise return null or throw an exception.
   public V get(K key) { }

   // If key is valid then sets its value to null. Does not remove it.
   // Otherwise, do nothing or throw an exception.
   public void remove(K key) { }

   // Sets all values to null but does not remove keys.
   public void clear() {}

   // Returns a set containing all of the keys.
   public Set<K> keySet() { }

I looked at the HashMap source and it looks like you would be able to pull out a lot of code around load factors and capacities and simplify some of the other code because the size would be known at creation time.

Anyone have any thoughts on how such a thing might be designed to take advantage of the fact that the keys are all known up front? Could you get rid of the hashing function altogether?

I do recognize that this is a micro optimisation and may or may not be worth the effort for a given application but the question seemed interesting and so I thought I would ask if others had any ideas.
Offline Best Username Ever

Junior Devvie

« Reply #1 - Posted 2012-12-16 02:55:35 »

I have wanted such a class for a while now. I can think of three ways to do this. For small maps, just use an array. For large maps I only can think of two. 1) Construct a minimal perfect hash function on the keyset at runtime. Huh 2) Put them in a sorted array and use a binary search for key look ups. Stare
Offline Nate

« JGO Bitwise Duke »

Medals: 167
Projects: 4
Exp: 14 years

Esoteric Software

« Reply #2 - Posted 2012-12-16 04:25:25 »

If you create the map and then only do gets, a cuckoo map would be an option. It essentially spends effort during puts to make gets efficient. libgdx has an implementation and also an identity map and a few for primitive keys/values (all based on cuckoo).

Otherwise you can give each of your keys an ordinal and then use an array for the values. This isn't general purpose of course.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline sproingie

JGO Kernel

Medals: 202

« Reply #3 - Posted 2012-12-16 05:29:56 »

If you use any alternative Map implementation, you should profile to make sure it's saving you anything.  And yes, if all your use sites are static you can get rid of the hashing altogether and just use the values themselves (or references to them, basically the same thing in java), but that's kind of a trivial use case.  Best you might otherwise do is use Enums and let the JIT optimize the switch table.
Pages: [1]
  ignore  |  Print  

hadezbladez (361 views)
2018-11-16 13:46:03

hadezbladez (194 views)
2018-11-16 13:41:33

hadezbladez (363 views)
2018-11-16 13:35:35

hadezbladez (91 views)
2018-11-16 13:32:03

EgonOlsen (2193 views)
2018-06-10 19:43:48

EgonOlsen (2229 views)
2018-06-10 19:43:44

EgonOlsen (1386 views)
2018-06-10 19:43:20

DesertCoockie (2023 views)
2018-05-13 18:23:11

nelsongames (1677 views)
2018-04-24 18:15:36

nelsongames (2313 views)
2018-04-24 18:14:32
Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08

Deployment and Packaging
by gouessej
2018-08-22 08:03:45

Deployment and Packaging
by philfrei
2018-08-20 02:33:38

Deployment and Packaging
by philfrei
2018-08-20 02:29:55

Deployment and Packaging
by philfrei
2018-08-19 23:56:20

Deployment and Packaging
by philfrei
2018-08-19 23:54:46 is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!