Most efficient data structure

Hey guys, so I will be needing some kind of data structure to be storing integers. I basically need something in which finding the player's node and mutating a value within that node is quick and efficient. I don't necessarily need something thats quick with adding nodes, just editing the values within them. Any advice?

I'm trying out hashmaps. Would that be considered O(log N) when searching for a node? However, it will also be stored in an ArrayList (though I may also switch that into another hashmap if the O-notation is smaller in practice).

EDIT by Moderator: merged posts, please use the edit button instead of double posting.

 

A well-designed hash has a theoretic constant-time lookup, i.e. O(1) - lookup time will be constant regardless of the size of the hash. Java's hash map should be considered reasonably well-designed, and if you're looking for a fast player->integer lookup, it's the right data structure to use. Of course, actual lookup times vary somewhat with hashes, since collisions do occur. http://stackoverflow.com/questions/1055243/is-a-java-hashmap-really-o1

(O(log n) complexity would be typically seen in a structure like a binary tree - better than a linear search which is O(n), but not as good as O(1)).

 

I'm not familiar with the concept of collisions. I'm reading through the provided thread, but I don't understand it. Thank you for replying and assisting with this.

EDIT: I didn't imagine there'd be any data structure with a search/get method of O(1). Pretty fascinating. I'm in a class where we've had to build our own data structures, and the fastest I've seen is O(log N). A-freakin-mazing.

 

Bit of a simplification here, but: one implementation of a hash table would be an array of linked lists.

When you want to look up an element (say, a player name), you compute a hash of that player name. (This is what the Java Object#hashCode() method does). That hash is used as an index into your hash table array. Of course, two or more objects may end up with the same hash code, which is where you get collisions. In that case, you'll have multiple elements in one slot of the array (also referred to as a bucket), which is where the linked list comes in.

The goal of a really efficient hash table is to minimise the number of collisions. Collisions reduce insertion & lookup performance. The ways of a achieving this are a) choose a good hashCode() method for the class you're storing, and b) get the size of the array that backs the hash table right. Java mostly does both a) and b) for you, although if you're implementing a custom class whose objects will be used as hash keys, then implementing a good hashCode() method yourself is vital.

Also worth reading http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html to see how Java hash tables can be tuned (see the disucssion on initial size and load factor).

 

I think I kind of understand. So the key is translated into hashcode? (I guess I really don't need to know this, but it's an interesting topic).

Now I'm trying to implement multiple arenas with two teams each and multiple players. Would this data structure make sense? A hash table which stores arenas, which stores an arraylist of teams, which stores stores a hash table of players. Basically it would look like this:

HashTable<Arenas, Teams<Player, PlayerStats>>

There are really only going to be two teams max per arena, so I'm not sure if an ArrayList is really necessary (maybe an Array instead).

By the way, thank you for really taking time to explain these things. It's really helpful and interesting to know about different types of data structures and their practical uses.

 

So you have:

• One or more Arena objects, each containing two Team objects
• A Team object contains a set of players, and their stats

I'd probably just have a field in the Arena object like

PHP:

Team[] teams = new Team[2];


A simple 2-element array suffices there.

The Team object contains a collection of players (the Set class could be useful here), and you might find it works better to store players and their stats separately from the team they're in; allows for flexibility in moving players between teams (and thinking about it, a player's stats are a property of the player, not of his team).

I'd also recommend always storing player names, not actual Bukkit Player objects. That can lead to memory leaks etc. when players log out & in again.

 

desht

I see. I was thinking of having a hashtable for players in each arena only because I thought it'd be easier to update stats. Then after then end of each arena game, submit each player's stats into mySQL or SQLite database for overall game stats. I'm not sure if my thinking makes sense, so please critique me on that. I'll definitely look into using a Set, because that definitely sounds practical (and I notice there's a hashset too!). If I do make a single hashtable for all online players, then I suppose I can easily add currentArena and currentTeam references and base my search off that.