View source for Applied Programming/Dictionaries and Sets

{{TOCright}}
== Overview ==

== Data Structure ==
In [[computer science]], a '''data structure''' is a data organization, management, and storage format that enables efficient access and modification.<ref>{{Cite book|title=Introduction to Algorithms, Third Edition|last=Cormen|first=Thomas H.|isbn=978-0262033848|publisher=The MIT Press|date=2009|url=https://dl.acm.org/citation.cfm?id=1614191|last2=Leiserson|first2=Charles E.|last3=Rivest|first3=Ronald L.|last4=Stein|first4=Clifford|edition=3rd}}</ref><ref>{{cite book|title=Dictionary of Algorithms and Data Structures [online]|last1=Black|first1=Paul E.|publisher=National Institute of Standards and Technology|date=15 December 2004|access-date=2018-11-06|chapter=data structure|chapter-url=https://xlinux.nist.gov/dads/HTML/datastructur.html|editor1-last=Pieterse|editor1-first=Vreda|editor2-last=Black|editor2-first=Paul E.}}</ref><ref>{{cite encyclopedia|encyclopedia=Encyclopaedia Britannica|title=Data structure|url=https://www.britannica.com/technology/data-structure|access-date=2018-11-06|date=17 April 2017}}</ref> More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.<ref>{{Cite book|title=Encyclopedia of Computer Science|last=Wegner|first=Peter|isbn=978-0470864128|publisher=John Wiley and Sons|date=2003-08-29|location=Chichester, UK|url=http://dl.acm.org/citation.cfm?id=1074100.1074312|last2=Reilly|first2=Edwin D.|pages=507–512}}</ref> 

Data structures provide a means to manage large amounts of data efficiently for uses such as large databases and internet indexing services. Usually, efficient data structures are key to designing efficient algorithms. Some formal design methods and [[Programming language|programming languages]] emphasize data structures, rather than algorithms, as the key organizing factor in software design. Data structures can be used to organize the storage and retrieval of information stored in both main memory and secondary memory.<ref>{{cite web|title=When data is too big to fit into the main memory|url=http://homes.sice.indiana.edu/yye/lab/teaching/spring2014-C343/datatoobig.php|website=homes.sice.indiana.edu}}</ref>

Data structures are generally based on the ability of a [[computer]] to fetch and store data at any place in its memory, specified by a pointer—a bit string, representing a memory address, that can be itself stored in memory and manipulated by the program. Thus, the array and record data structures are based on computing the addresses of data items with arithmetic operations, while the linked data structures are based on storing addresses of data items within the structure itself.

The implementation of a data structure usually requires writing a set of procedures that create and manipulate instances of that structure. The efficiency of a data structure cannot be analyzed separately from those operations. This observation motivates the theoretical concept of an abstract data type, a data structure that is defined indirectly by the operations that may be performed on it, and the mathematical properties of those operations (including their space and time cost).<ref>{{Cite book|title=Advanced biotechnology : For B Sc and M Sc students of biotechnology and other biological sciences.|last=Dubey, R. C.|isbn=978-81-219-4290-4|publisher=S Chand|date=2014|location=New Delhi|oclc=883695533}}</ref>

There are numerous types of data structures, generally built upon simpler primitive data types:<ref>{{Cite book|title=Data structures|last=Seymour|first=Lipschutz|isbn=9781259029967|publisher=McGraw Hill Education|date=2014|location=New Delhi, India|edition=Revised first|oclc=927793728}}</ref>

* An ''array'' is a number of elements in a specific order, typically all of the same type (depending on the language, individual elements may either all be forced to be the same type, or may be of almost any type). Elements are accessed using an integer index to specify which element is required. Typical implementations allocate contiguous memory words for the elements of arrays (but this is not always a necessity). Arrays may be fixed-length or resizable.
* A ''linked list'' (also just called ''list'') is a linear collection of data elements of any type, called nodes, where each node has itself a value, and points to the next node in the linked list. The principal advantage of a linked list over an array is that values can always be efficiently inserted and removed without relocating the rest of the list. Certain other operations, such as random access to a certain element, are however slower on lists than on arrays.
* A ''record'' (also called ''tuple'' or ''struct'') is an aggregate data structure. A record is a value that contains other values, typically in fixed number and sequence and typically indexed by names. The elements of records are usually called ''fields'' or ''members''.
* A ''union'' is a data structure that specifies which of a number of permitted primitive types may be stored in its instances, e.g. ''float'' or ''long integer''. Contrast with a record, which could be defined to contain a float ''and'' an integer; whereas in a union, there is only one value at a time. Enough space is allocated to contain the widest member datatype.
* A ''tagged union'' (also called ''variant'', ''variant record'', ''discriminated union'', or ''disjoint union'') contains an additional field indicating its current type, for enhanced type safety.
* An ''object'' is a data structure that contains data fields, like a record does, as well as various methods which operate on the data contents. An object is an in-memory instance of a class from a taxonomy. In the context of object-oriented programming, records are known as plain old data structures to distinguish them from objects.<ref>{{cite web|url=http://www.fnal.gov/docs/working-groups/fpcltf/Pkg/ISOcxx/doc/POD.html|access-date=6 December 2016|title=C++ Language Note: POD Types|author=Walter E. Brown|publisher=Fermi National Accelerator Laboratory|date=September 29, 1999|archive-url=https://web.archive.org/web/20161203130543/http://www.fnal.gov/docs/working-groups/fpcltf/Pkg/ISOcxx/doc/POD.html|archive-date=2016-12-03}}</ref><ref>https://en.wikipedia.org/wiki/Data_structure</ref>

== Dictionary (Data Structure) ==
In [[computer science]], an '''associative array''', '''map''', '''symbol table''', or '''dictionary''' is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.

Operations associated with this data type allow:<ref name="gt">{{citation|contribution=9.1 The Map Abstract Data Type|title=Data Structures & Algorithms in Java|last1=Goodrich|first1=Michael T.|author1-link=Michael T. Goodrich|last2=Tamassia|first2=Roberto|author2-link=Roberto Tamassia|publisher=Wiley|edition=4th|year=2006|pages=368–371}}</ref><ref name="ms">{{citation|contribution=4 Hash Tables and Associative Arrays|title=Algorithms and Data Structures: The Basic Toolbox|first1=Kurt|last1=Mehlhorn|author1-link=Kurt Mehlhorn|first2=Peter|last2=Sanders|author2-link=Peter Sanders (computer scientist)|publisher=Springer|year=2008|pages=81–98|url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/HashTables.pdf}}</ref>

* the addition of a pair to the collection;
* the removal of a pair from the collection;
* the modification of an existing pair;
* the lookup of a value associated with a particular key.

Implementing associative arrays poses the '''dictionary problem''', a classic computer science problem: the task of designing a data structure that maintains a set of data during 'search', 'delete', and 'insert' operations.<ref>{{cite journal|title=Optimal Bounds on the Dictionary Problem|last=Andersson|first=Arne|journal=Proc. Symposium on Optimal Algorithms|series=Lecture Notes in Computer Science|date=1989|volume=401|pages=106–114|publisher=Springer Verlag|doi=10.1007/3-540-51859-2_10|isbn=978-3-540-51859-4}}</ref> The two major solutions to the dictionary problem are a hash table and a search tree.<ref name="gt" /><ref name="ms" /><ref name="clrs">{{citation|last1=Cormen|last4=Stein|chapter=11 Hash Tables|isbn=0-262-03293-7|publisher=MIT Press and McGraw-Hill|year=2001|edition=2nd|title=Introduction to Algorithms|first4=Clifford|author4-link=Clifford Stein|first1=Thomas H.|first3=Ronald L.|last3=Rivest|author3-link=Ron Rivest|first2=Charles E.|last2=Leiserson|author2-link=Charles E. Leiserson|author1-link=Thomas H. Cormen|pages=221–252}}.</ref><ref name="dietzfelbinger">Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R. E. 1994. [http://www.arl.wustl.edu/~sailesh/download_files/Limited_Edition/hash/Dynamic%20Perfect%20Hashing-%20Upper%20and%20Lower%20Bounds.pdf "Dynamic Perfect Hashing: Upper and Lower Bounds"] . SIAM J. Comput. 23, 4 (Aug. 1994), 738-761. http://portal.acm.org/citation.cfm?id=182370 {{doi|10.1137/S0097539791194094}}</ref> In some cases it is also possible to solve the problem using directly addressed arrays, binary search trees, or other more specialized structures.

Many programming languages include associative arrays as primitive data types, and they are available in software libraries for many others. Content-addressable memory is a form of direct hardware-level support for associative arrays.

Associative arrays have many applications including such fundamental programming patterns as memoization<!--NOT a misspelling--> and the decorator pattern.<ref name="decorator">{{harvtxt|Goodrich|Tamassia|2006}}, pp. 597–599.</ref>

The name does not come from the associative property known in mathematics. Rather, it arises from the fact that we associate values with keys.

In an associative array, the association between a key and a value is often known as a "mapping", and the same word mapping may also be used to refer to the process of creating a new association.

The operations that are usually defined for an associative array are:<ref name="gt" /><ref name="ms" />

* '''Add''' or '''insert''': add a new <math>(key, value)</math> pair to the collection, mapping the new key to its new value. The arguments to this operation are the key and the value.
* '''Reassign''': replace the value in one of the <math>(key, value)</math> pairs that are already in the collection, mapping an existing key to a new value. As with an insertion, the arguments to this operation are the key and the value.
* '''Remove''' or '''delete''': remove a <math>(key, value)</math> pair from the collection, unmapping a given key from its value. The argument to this operation is the key.
* '''Lookup''': find the value (if any) that is bound to a given key. The argument to this operation is the key, and the value is returned from the operation. If no value is found, some associative array implementations raise an exception, while others create a pair with the given key and the default value of the value type (zero, empty container...).

Often then instead of add or reassign there is a single '''set''' operation that adds a new <math>(key, value)</math> pair if one does not already exist, and otherwise reassigns it.

In addition, associative arrays may also include other operations such as determining the number of mappings or constructing an iterator to loop over all the mappings. Usually, for such an operation, the order in which the mappings are returned may be implementation-defined.

A multimap generalizes an associative array by allowing multiple values to be associated with a single key.<ref>{{harvtxt|Goodrich|Tamassia|2006}}, pp. 389–397.</ref> A bidirectional map is a related abstract data type in which the mappings operate in both directions: each value must be associated with a unique key, and a second lookup operation takes a value as an argument and looks up the key associated with that value.

Suppose that the set of loans made by a library is represented in a data structure.  Each book in a library may be checked out only by a single library patron at a time.  However, a single patron may be able to check out multiple books.  Therefore, the information about which books are checked out to which patrons may be represented by an associative array, in which the books are the keys and the patrons are the values.  Using notation from Python or JSON, the data structure would be:
<syntaxhighlight lang="javascript">
{
    "Pride and Prejudice": "Alice",
    "Wuthering Heights": "Alice",
    "Great Expectations": "John"
}
</syntaxhighlight>A lookup operation on the key "Great Expectations" would return "John".  If John returns his book, that would cause a deletion operation, and if Pat checks out a book, that would cause an insertion operation, leading to a different state:
<syntaxhighlight lang="javascript">
{
    "Pride and Prejudice": "Alice",
    "The Brothers Karamazov": "Pat",
    "Wuthering Heights": "Alice"
}
</syntaxhighlight>
The basic definition of the dictionary does not mandate an order. To guarantee a fixed order of enumeration, ordered versions of the associative array are often used. There are two senses of an ordered dictionary:

* The order of enumeration is always deterministic for a given set of keys by sorting. This is the case for tree-based implementations, one representative being the <code><map></code> container of C++.
* The order of enumeration is key-independent and is instead based on the order of insertion. This is the case for the "ordered dictionary" in .NET Framework and Python.

The latter sense of ordered dictionaries are more commonly encountered. They can be implemented using an association list, or by overlaying a doubly linked list on top of a normal dictionary. The latter approach, as used by CPython before version 3.6, has the advantage of keeping the potentially better complexity of another implementation. CPython 3.6+ makes dictionaries ordered by splitting the hash table into an insertion-ordered array of k-v pairs and a sparse array ("hash table") of indices.<ref>https://en.wikipedia.org/wiki/Associative_array</ref>

== Hash Table ==

== Key-Value Database ==

'''What is it?'''

A key-value database is a type of nonrelational database that uses a simple key-value method to store data. A key-value database stores data as a collection of key-value pairs in which a key serves as a unique identifier. Both keys and values can be anything, ranging from simple objects to complex compound objects. Key-value databases are highly partitionable and allow horizontal scaling at scales that other types of databases cannot achieve.<ref>https://www.xspdf.com/resolution/21031178.html</ref>

'''Compared to relational databases?'''

Relational databases organize data using tables. Tables are structures that impose a schema on the records that they hold. Each column within a table has a name and a data type. Each row represents an individual record or data item within the table, which contains values for each of the columns. Relational databases get their name from mathematical relationships that use tuples (like the rows in a table) to represent ordered sets of data.<ref>https://www.prisma.io/dataguide/intro/comparing-database-types#nosql-databases-modern-alternatives-for-data-that-doesnt-fit-the-relational-paradigm</ref>

'''What does this mean?'''

Key–value databases work in a very different fashion from the better known relational databases (RDB). RDBs predefine the data structure in the database as a series of tables containing fields with well defined data types. Exposing the data types to the database program allows it to apply a number of optimizations. In contrast, key–value systems treat the data as a single opaque collection, which may have different fields for every record. This offers considerable flexibility and more closely follows modern concepts like object-oriented programming. Because optional values are not represented by placeholders or input parameters, as in most RDBs, key–value databases often use far less memory to store the same database, which can lead to large performance gains in certain workloads.<ref>{{w|Key-value database}}</ref>

== Set (Abstract Data Type) ==

== Activities ==
1) Write a program that creates a dictionary where the keys are even integers between 2 and 20 and the values are the corresponding key multiplied by the odd integer before it. 

Example output: {2: 2, 4: 12, 6: 30, 8: 56...}

2) Write a program that takes two lists and merges them into a single dictionary. 

Example:
<syntaxhighlight lang="Python">
list_1 = [5, 10, 15, 20] 

list_2 = ['a', 'b', 'c', 'd']
</syntaxhighlight>
Result: {5: 'a', 10: 'b', 15: 'c', 20: 'd'}

3) Write a program that searches for the minimum value and returns the corresponding key.

Example:
<syntaxhighlight lang="Python">
prices = {'Popcorn': 1.50, 'Soda': 1.00, 'Hotdog': 1.25, 'Nachos': 0.75}
</syntaxhighlight>
Result: 'Nachos'

== Key Terms ==
'''Dictionary / Associative array / Hash / Map''' - An abstract data type that can hold data in ''(key, value)'' pairs.<ref>https://brilliant.org/wiki/associative-arrays/</ref>

'''Frozen Set''' - A native data type in Python that have the qualities of sets — including class methods — but are immutable like tuples.<ref name=":0">https://betterprogramming.pub/what-are-frozen-sets-in-python-88f8a15a28dc</ref>

'''Hash collision''' - Occur when two entries are generated using the same index key. This has a high chance of occurring when hashing a random subset of a large set of possible keys.<ref>https://en.wikipedia.org/wiki/Hash_table</ref>

'''Hash table''' - A type of data structure that stores key-value pairs. The key is sent to a hash function that performs arithmetic operations on it. The result (commonly called the ''hash value'' or ''hash'') is the index of the key-value pair in the hash table.<ref>https://www.educative.io/edpresso/what-is-a-hash-table</ref>

'''Key''' - A field, or combination of fields, in a database table used to retrieve and sort rows in the table based on certain requirements. Keys are defined to speed up access to data and, in many cases, to create links between different tables.<ref>https://www.techopedia.com/definition/1780/key</ref>

'''Load factor''' - A critical statistic for hash tables that references how quickly the hash table can be accessed. A higher load factor indicates the table may become slower or fail to work at all.

'''Merge algorithm''' - A family of algorithms that take multiple sorted lists as input and produce a single list as output, containing all the elements of the inputs lists in sorted order. These algorithms are used as subroutines in various sorting algorithms, most famously merge sort.<ref>https://en.wikipedia.org/wiki/Merge_algorithm</ref>

'''Multimap''' - A generalization of a map or associative array abstract data type in which more than one value may be associated with and returned for a given key.<ref>https://en.wikipedia.org/wiki/Multimap</ref>

'''Multiset''' - A type of associative containers similar to set, with an exception that multiple elements can have same values.<ref>https://www.geeksforgeeks.org/multiset-in-cpp-stl/</ref>

'''Serialization''' - Produces a text or binary representation of the original objects that can be written directly to a file and offers a solution to use associative arrays in permanent form.<ref>https://en.wikipedia.org/wiki/Associative_array</ref>

'''Set''' - An unordered, mutable data type where each value must be unique.<ref name=":0" />

== References ==
{{Reflist}}
{{Status|50%}}
{{BookCat}}