# Best way to create a HASH TABLE out of an ARRAY in Swift, please?

Hey Team,

I wrote some working Swift code! (Yay!)

My investigation into building and using a HASH TABLE in Swift brought me here :

But that looks like a heckin’ of a lot of work and was written six years ago.

The approach I took was to use the fact that Dictionary conforms to Hashable and therefore can function as a Hash Table. (Am I right about this?)

It works, but is this the BEST or MOST APPROPRIATE way to do this?

(Java and Python3 solutions are presented for reference.)

Thank you for your time and attention.

``````// Project : Code Interview Problems and Solutions (CIPS)
//
// Problem : Two Sum
//
// Difficulty : Easy
//
// Given an array of integers nums and an integer target,
// return indices of the two numbers such that they add up to target.
//
// You may assume that each input would have exactly one solution,
// and you may not use the same element twice.
//
// You can return the answer in any order.
//
// Example 1:
//
// Input: nums = [2,7,11,15], target = 9
// Output: [0,1]
// Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
//
// Example 2:
//
// Input: nums = [3,2,4], target = 6
// Output: [1,2]
//
// Example 3:
//
// Input: nums = [3,3], target = 6
// Output: [0,1]
//
// Constraints:
//
// 2 <= nums.length <= 10^4
// -10^9 <= nums[i] <= 10^9
// -10^9 <= target <= 10^9
// Only one valid answer exists.
//
// Follow-up:
//
// Can you come up with an algorithm that is less than O(n^2) time complexity?
//
// Approach : One Pass Hash Table
//
// Algorithm
//
// Iterate through nums.
//     Put nums-values and nums-indices into hash table.
//     Check if current nums-value's complement is in hash table.
//     If found, return solution
//
// Java Code
//
// class Solution {
//     public int[] twoSum(int[] nums, int target) {
//     Map<Integer, Integer> map = new HashMap<>();
//     for (int i = 0; i < nums.length; i++) {
//         int complement = target - nums[i];
//         if (map.containsKey(complement)) {
//             return new int[] { map.get(complement), i};
//         }
//         map.put(nums[i], i);
//     }
//     // If no solution, return null
//     return null;
// }
//
// Python3 Code
//
// class Solution:
//     def twoSum(self, nums: List[int], target: int) -> List[int]:
//         hashmap = {}
//         for i in range(len(nums)):
//             complement = target - nums[i]
//             if complement in hashmap:
//                 return [i, hashmap[complement]]
//             hashmap[nums[i]] = i
//
// Swift Code
//
// Note: Dictionary conforms to Hashable and performs as a hash table.

class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var dict: Dictionary<Int, Int> = [:]
for i in 0 ..< nums.count {
let complement:Int = target - nums[i]
var containTest = dict.contains { \$0.value == complement }
if containTest {
let key = dict.filter{ \$0.value == complement }.keys.first!
return [key, i]
}
dict[i] = nums[i]
}
// If no solution, return nil
var arr = [Int]()
return arr
}
}

var tester = Solution()

// Testcase 1
tester.twoSum([2,7,11,15], 9) // Returns [0, 1]

// Testcase 2
tester.twoSum([3,2,4], 6) // Returns [1, 2]

// Testcase 3
tester.twoSum([3,3], 6) // Returns [0, 1]

// End of problem and solution.

``````

Thanks, again.

Hey Marie, welcome to the site.

Please unbold your post. It looks like you're yelling. Plus, it's counter productive. If everything is emphasized, nothing is emphasized

that Dictionary conforms to Hashable and therefore can function as a Hash Table. (Am I right about this?)

Not quite. `Dictionary` is a hash-table based data structure. In Python they call it `dict`, in C++ it's `std::unordered_map`, `Hash` in Ruby, `HashMap` in Java, and so on.

Conforming to `Hashable` means that your type can be hashed. Among other things, this lets your values be used as elements of a Set, or keys of a Dictionary. For example, you can have `[[Int: Bool]: String]`. That is, if you hypothetically have dictionaries whose keys are integers and values are booleans, you can use those dictionaries as keys inside other dictionaries, or as members of sets.

The rest of your question is a bit unclear to me. The TwoSum problem and solution you propose is merely using a Dictionary, but the article you posted is about how `Dictionary` works under the hood, and how one might go about building it for themselves.

4 Likes

Thank you for the reply, @AlexanderM

The bold was copied over from TextEdit accidentally. I unbolded everything.

I will retry my question:

How would you write this line of Java code in Swift:

``````Map<Integer, Integer> map = new HashMap<>();
``````

or

How would you write this line of Python3 code in Swift :

``````hashmap = {}
``````

Thank you.

Hi Marie

If you're asking how would a swift version of the python/java code for the two sum solver look like, here's an example:

``````func findTwoSumTarget(_ target: Int, in array: [Int]) -> (Int, Int)? {
var lookup: [Int: Int] = [:]

for (index, value) in array.enumerated() {
guard value < target else {
continue
}

if let complementIndex = lookup[value] {
return (index, complementIndex)
}

let complement = target - value
lookup[complement] = index
}

return nil
}
``````

This code runs about twice as fast as your original implementation (which is not bad by the way)

Few things to note:

• There's no need to return an array, you can return a tuple with the 2 indices
• you can use .enumerated() to return an iterator for the for loop `for (index, value) in array.enumerated()` so that you don't have to access the array by index at any time
• you can continue the loop if the current value is greater than the target because there's no way that value will form part of the sum
• you can check if a dictionary contains a value simply by checking if that dictionary[key] is not null. That's what `if let complementIndex = lookup[value]` does with the added benefit that you don't have to filter afterwards and get the keys

.contains and .filter are there for more complex expressions. Checking if a dictionary has a value for a specific key is a lot simpler :)

Hope this helped

1 Like

I'll break this down in a bit more detail.

`Map` in Java is an interface (their equivalent of a Swift `protocol`). `HashMap` is one class that implements the `Map` interface, but there are also others. The Swift counterpart to `HashMap` is `Dictionary`, but there's no counterpart to `Map`. So the equivalent Swift code would be more like this Java:

``````HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
``````

In Swift, that would look like:

``````let map: Dictionary<Int, Int> = Dictionary<Int, Int>()
``````

Idomatic Swift code would typically use type inference to shorten it down to:

``````let map = [Int: Int]()
``````

Where:

1. Type inference removes the need for the type annotation (`: Dictionary<Int, Int>`)
2. `[Int: Int]()` uses syntactic sugar. `[K: V]` is equivalent to `Dictionary<K, V>`
2 Likes

This isn't the only form that's common; I've also seen

``````let map2: [Int: Int] = [:] // Equivalent to {} in Python
let map3: [Int: Int] = .init()
``````

That last one is definitely more obscure but I have seen it, for example, as a default argument to an initializer.

As a sidenote, using `let` here prevents you from modifying it in any way (more strict than Java `final`; similar to C++ `const`), so you probably want `var` instead.

2 Likes

First of all, thank you, @iGabriel for some HUGE clues.

A few things . . .

• I believe the "value < target" test should be "value <= target" because it is possible to have COMPLEMENT = 0 for example an "8 + 0 = 8" solution.

• The return value has to be an array and can't be a tuple per problem specifications. The fixed header was provided as follows:

``````class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
``````
• I moved things around so they would match the "build complement" first before the "test" portion of the program.

• I thought that I could lookup a Dictionary table row by VALUE, when in fact it can only be done by KEY.

I was unable to find any way to do something like `var someVar = someDict[value]` instead of `var someVar = someDict[key]` using the square bracket syntax.

If anyone knows how to do this, or if this is possible to lookup a dictionary row by value using the square brackets, please advise.

So, to make the whole thing work, the hash table build had to be `dictionary[value] = index` instead of `dictionary[index] = value` which feels logically backwards to me, but it works in this case because both sets, index and value, have unique values with no duplicates, so it doesn't matter to the computer.

(Apologies for all the debug print statements, I was stuck on this issue for quite a while.)

• I'm not sure if
``````      let complement = target - value
lookup[complement] = index
``````

Was the proper way to build the hash table. I believe the hash table was supposed to be built as an identical copy of the input array `nums`.

Thank you, again, for all your fine clues and wisdom.

Here is Version 2 :

``````// Version 2

class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var dictionary: [Int: Int] = [:]
for (index, value) in nums.enumerated(){
//            print("for index: \(index) value: \(value)")
guard value <= target else {
continue
}
var complement = target - value
//            print("var target: \(target) - value: \(value) = complement: \(complement)")
//            print("PREIFLET dictionary: \(dictionary)")
//            print("PREIFLET dictionary[complement]: \(dictionary[complement] ?? 666)")
if let complementIndex = dictionary[complement] {
//                print("RETURN")
return [complementIndex, index]
}

dictionary[value] = index
//            print("POSTASSIGN dictionary: \(dictionary)")
}
return [Int]()
}
}

var tester = Solution()

// Testcase 1
tester.twoSum([2,7,11,15], 9) // Returns [0, 1]

// Testcase 2
tester.twoSum([3,2,4], 6) // Returns [1, 2]

// Testcase 3
tester.twoSum([3,3], 6) // Returns [0, 1]

// Testcase 4
tester.twoSum([9,8,7,6,0,2,4], 4) // Returns [4, 6]

// Testcase 5
tester.twoSum([0,1,2,3,4], 100) // Returns []

// End of problem and solution.
``````