"Explore efficient data structure implementation in Delphi by Stefan Glienke, covering hash tables, TDictionary, structure of RTL hash tables, and techniques for making dictionaries ordered."
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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Efficient Efficientdata reimplementing reimplementinga a dictionary datastructures structuresin Delphi dictionary in Delphi STEFAN GLIENKE
About me Experience in Turbo Pascal and Delphi since 1997 Education as software developer Participation in several open source projects Embarcadero MVP since 2014 and MVP of the year 2015 Specialized in following areas Development of logic and data layers Software design and architecture Clean code Lead developer of Spring4D
What is a hash table? Key and Value mapping 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 Values go into an array Marco Marco Stefan Paolo Paolo Paolo Hash function to get an array index out of the Key used to do insertions and lookup Dealing with hash collisions when more than one item would go into the same index Creating array or linked list at that index to store more than one item Probing looking for the next free slot Order of items is based on the hash function which is not easily predictable
TDictionary<TKey,TValue> from RTL Storing an array of Key/Value pairs plus the HashCode Doing linear probing if slot is occupied Removal is a bit tricky as gaps need to be filled in order to not break probing (see comment in DoRemove)
Making the dictionary ordered Keep items in insertion order (like in a list where you add/append to the end) Possibilities: Maintain ordered key List (this was done in Spring4D 1.2 in the TOrderedDictionary) Add previous and next pointers to the buckets to maintain order (LinkedHashMap<K,V> from Java) Split content into two arrays (dict in Python 3.6) item array holding the key/value pairs bucket array containing the indexes of entries in the item array
Structure of the new dictionary Bucket Index Item Index Item Index Key Value 0 1 0 '0' 0 1 <empty> 1 '1' 1 2 <empty> 2 '2' 2 3 3 3 '3' 3 4 2 5 <empty> 6 0 7 <empty>
Performance considerations Store the hash in the items array If hash values differ items cannot be equal (comparing hashes it faster than item comparison) Indirection is affecting performance Solution: using some bytes from the ItemIndex for the HashCode
