Tell me about hash tables and their basic working principle.

A hash table (hash map) is a data structure that implements an associative array, mapping keys to values.

Basic working principle:

1. Hashing: A hash code is computed for each key — a fixed-size numerical value using a hash function. A good hash function distributes hash codes evenly across the output range.
2. Indexing: The computed hash code is used to determine an index (position) in the array where the corresponding value will be stored. Often, the hash code modulo the array size (hash(key) % array_size) gives the final index.
3. Storage: The pair (key, value) is stored at the calculated index in the array.
4. Search: To find a value by key, the hash code of the key is recomputed, the index is determined, and the value is retrieved from that index.
5. Collisions: Occur when different keys have the same hash code. Various methods exist to resolve collisions:
   • Chaining: Each array index stores a list (or another data structure) containing all pairs (key, value) whose hash codes lead to that index.
   • Open Addressing: When a collision occurs, another free spot in the array is sought according to a specific rule (linear probing, quadratic probing, double hashing).

Advantages:

• On average, insertion, deletion, and search operations have O(1) complexity if the hash function is good and collisions are rare.

Disadvantages:

• The worst-case performance can be O(n) if all keys hash to the same index (e.g., with a poor hash function or many collisions).
• Additional memory is required for the array and possibly for collision resolution.

In Swift, hash tables are implemented with the Dictionary type.

// Example of using Dictionary in Swift
var myDictionary: [String: Int] = ["apple": 1, "banana": 2, "orange": 3]

// Access by key
let value = myDictionary["banana"] // Gets Optional(2)

// Add/update
myDictionary["grape"] = 4 // Adds a new pair
myDictionary["apple"] = 10 // Updates the value for key "apple"

// Remove
myDictionary["orange"] = nil // Removes the pair with key "orange"