Hashing Project - MMORPG

Launched November 2023

Tags

  • Back End
  • Data Structures and Algorithms
  • Documentation
  • Java
  • Software Development

Purpose:To practice and demonstrate proficiency in creating, manipulating and utilizing hash tables and concepts around hashing using Java programming

Knowledge Goals: Hash Tables, Hashing, Collision Resolution (Linear Probing, Double Hashing, Separate Chaining)

Summary

The purpose of this project was to create a data storage model for a massive multiplayer online roleplaying game (MMORPG), a game where players sign on and play with other players around the world in a virtual setting. We wanted to emulate the records of this MMORPG. Each record contains data about a player. So whenever someone joins the game, an account is created and assigned a unique record number. This number is used to locate a Character record.

We indexed Character objects using a hash function, handling collisions and searching using separate chaining, although we also considered quadratic probing and double hashing.

Because the game is so popular, this MMORPG rarely gets a request to delete an account. In this scenario, the number of Characters increased to the thousands and the developers realized they could not keep the entire database in memory so they chose to use an indexing scheme. In this scheme, the Character's name and record number would be stored in memory, but their entire record would only be loaded if they were logged into the game.

We implemented this database system using a list and a Hashed Dictionary. The list stored each player as an instance of the Character class. Each time a new player account is created, it is added to the end of the list so that its position is also its record number. If an account is deleted, its position in the list is set to null so the positions of the other entries do not change. For the dictionary, each key is a Character's name, and each value is a record number (list position) to point to the Character's details in the list. The index is hashed. We added two names that cause collision in order to demonstrate collision resolution with separate chaining. We chose to model the list using Java's ArrayList.

UML Class Diagram

UML diagram showing fields and methods of various classes including Character, CharacterDatabase, and HashDictionary

Java Implementation

Interfaces

  • DictionaryInterfaceInterface for the hashed dictionary
    • add
    • remove
    • getValue
    • contains
    • getKeyIterator
    • getValueIterator
    • isEmpty
    • getSize
    • clear
  • CharacterDatabaseInterface Character Database interface
    • addCharacter(name, height, weight, moralAlign)
    • removeCharacter
    • getCharacter
    • getHashTable
    • printList

Classes

  • Character Character class that represents a player
    • Getter and setter methods for name, height, and weight
    • Moral alignment and health have a getter but not a setter as that is done through the methods below
    • heal
    • injure
    • change
    • toString
  • HashDictionary Hashed Dictionary implementation using separate chaining for collisions
    • displayHashTable
    • getHashIndex
    • getSecondHashIndex (only for DoubleHashing)
    • probe
    • locate
    • enlargeHashTable
    • isHashTableTooFull
    • getNextPrime
    • isPrime
    • checkIntegrity
    • checkCapacity
    • checkSize
    • KeyIterator class
    • ValueIterator class
    • TableEntry class
  • CharacterDatabase Contains the List and HashedDictionary, implements the interface
  • Main Runs the program

Output

We tested our MMORPG by doing the following:

  1. Created a new CharacterDatabase instance using its interface.
  2. Added a character with the name "FB" (and other attributes)
  3. Added a character with the name "Ea"
  4. Added a character with the name "Daegon"
  5. Added a character with the name "Gandalf" and moral alignment of 1.0
  6. Cleanly and clearly printed the Hash Table to verify characters were put in. Verified that the hash indices of FB and Ea were the same (collision!) and verified it was handled correctly.
  7. Removed the character Daegon.
  8. Printed the Hash Table to verify Daegon was removed.
  9. Printed the list and verified Daegon's place was replaced with null.
  10. Retrieved the character Gandalf and printed his character sheet (toString)
  11. Shifted Gandalf's alignment
  12. Used the injure method on Gandalf
  13. Used the heal method on Gandalf
  14. Printed Gandalf's Character Sheet again (toString) and verify everything changed.

Documentation

Used javadoc comments on functions to explain what they do. Where there is an interface, used @inheritDoc.

GitHubopens in new tabHire Now

Thanks for checking out my project!

Back to Portfolio

Thank you!

Thanks for checking out my work! If you've got a project or job you think suits me, contact me here, by email, or on LinkedIn.

Contact Me

Find Me

roryhackney@gmail.com
LinkedIn
GitHub
Resume

Thanks for dropping by!

Back to top