Understanding Data Structures and Hashing in Java

Data structures play a crucial role in organizing, iterating, adding, deleting, and searching data efficiently. Hash tables, linked lists, trees, and more are explored in this overview, highlighting their strengths and trade-offs. Hashing, collision resolution strategies, and the importance of a well-distributed hash function are discussed to optimize performance. Dive into the world of data structures and hashing to enhance your understanding of Java programming.

• Data Structures
• Hashing
• Java
• Performance
• Algorithms

adle339 Follow

Uploaded on Oct 03, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. IAT 265 Java Collections Jul 7, 2015 IAT 265 1

2. Data Structures With a collection of data, we often want to do many things Organize Iterate Add new Delete old Search Jul 7, 2015 IAT 265 2

3. Data Structures Some are built to enable fast searching Some enable fast insertion/deletion What LnkList Store Light Iterate simple Add O(1) Delete O(1) Search O(n) Tree Less light moderate O( lgN ) O( lgN + ) O(lgN) HashTable Medium difficult O(1) O(1) O(1) Jul 7, 2015 IAT 265 3

4. Hash Table An array in which items are not stored consecutively - their place of storage is calculated using the key and a hash function key entry 4 array index hash function Key 10 Hashed key: the result of applying a hash function to a key Keys and entries are scattered throughout the array 123 Jul 7, 2015 IAT 265 4

5. Hashing insert: compute location, insert TableNode; O(1) find: compute location, retrieve entry; O(1) remove: compute location, set it to null; O(1) key entry 4 10 123 Jul 7, 2015 IAT 265 5

6. Hashing example 10 stock details, 10 table positions key 85 85, apples entry Stock numbers between 0 and 1000 0 1 2 3 4 5 6 7 8 9 Use hash function: stock no. / 100 What if we now insert stock no. 350? Position 3 is occupied: there is a collision 323 323, guava 462 462, pears 350 350, oranges Collision resolution strategy: insert in the next free position (linear probing) Given a stock number, we find stock by using the hash function again, and use the collision resolution strategy if necessary 912 912, papaya Jul 7, 2015 IAT 265 6

7. Hashing performance The hash function Ideally, it should distribute keys and entries evenly throughout the table It should minimize collisions, where the position given by the hash function is already occupied The collision resolution strategy Separate chaining: chain together several keys/entries in each position Open addressing: store the key/entry in a different position The size of the table Too big will waste memory; too small will increase collisions and may eventually force rehashing (copying into a larger table) Should be appropriate for the hash function used and a prime number is best Jul 7, 2015 IAT 265 7

8. Applications of Hashing Compilers use hash tables to keep track of declared variables A hash table can be used for on-line spelling checkers if misspelling detection (rather than correction) is important, an entire dictionary can be hashed and words checked in constant time Hash functions can be used to quickly check for inequality if two elements hash to different values they must be different Storing sparse data Jul 7, 2015 IAT 265 8

9. When to use hashing? Good if: Need many searches in a reasonably stable table Not So Good if Many insertions and deletions, If table traversals are needed Need things in sorted order More data than available memory Use a tree and store leaves on disk Jul 7, 2015 IAT 265 9

10. Java Collections A Java Collection class is a class that stores and organizes data Uses one of the algorithms mentioned in previous lectures Jul 7, 2015 IAT 265 10

11. Java Collections Framework A unified architecture for representing and manipulating collections: Interfaces: The means by which you access a collection class Independent of implementation details Implementations: The machinery behind the interface that does the work Concrete implementations Algorithms: Algorithms that run on collection classes: Searching and sorting Reusable Functionality Jul 7, 2015 IAT 265 11

12. Java Collections Framework Why? Reduces programming effort Increases program speed and quality Interoperable: You and I can pass data in collections between our code Jul 7, 2015 IAT 265 12

13. Interfaces Collection A group of objects (elements) This is a generic idea, there are more detailed Collection types that you actually use Set A collection with no duplicate elements SortedSet A Set in ascending order (Typically alphabetical or numeric order) Jul 7, 2015 IAT 265 13

14. Interfaces List An ordered collection May contain duplicates Can access by index (like ArrayList) Queue A collection that holds items in some order Typically FIFO (First in/First Out) Jul 7, 2015 IAT 265 14

15. Interfaces Map An collection that maps keys to values Think phone book May contain duplicates Can access by index (like ArrayList) SortedMap A Map in sorted order of keys Jul 7, 2015 IAT 265 15

16. Using a List Declare: ArrayList aList = new ArrayList(6); Methods you use: SomeClass item, newItem, existingItem ; item = (SomeClass)aList.get( i ); aList.add( newItem ); aList.remove( existingItem ); Jul 7, 2015 IAT 265 16

17. Using a HashMap HashMap<String,String> hm = new HashMap<String,String> (); hm.put( "Ava", "555-8976" ); hm.put( "Mary", "555-1238" ); hm.put( "Joe", "555-2121" ); String phone = hm.get( "Mary" ); Iterator I = hm.entrySet().iterator(); while( I.hasNext() ) { Map.Entry me = (Map.Entry)I.next(); print( me.getKey() + " is " ); println( me.getValue() ); } Jul 7, 2015 IAT 265 17

18. Using a TreeMap TreeMap<String,String> tm = new TreeMap<String,String>(); tm.put( "Ava", "555-8976" ); tm.put( "Mary", "555-1238" ); tm.put( "Joe", "555-2121" ); String phone = tm.get( "Mary" ); Iterator I = tm.entrySet().iterator(); while( I.hasNext() ) { Map.Entry me = (Map.Entry)I.next(); print( me.getKey() + " is " ); println( me.getValue() ); } Jul 7, 2015 IAT 265 18

19. Jul 7, 2015 IAT 265 19