# Arrays and Strings Flashcards

Hash Table

Maps keys to values for highly efficient lookup. A key is assigned a (not necessarily unique) hash code. The hash code is mapped to an index in an array with a hash function. Two hashes may map to the same index. At the index, a linked list stores key and value pairs to avoid collisions.

Hash Table Collisions

Collisions may occur b/c keys share the same hash code or hash codes map to the same index. Since each index comtains a linked list, simply traverse the list until the key is found. Worst case run time is O(N), but O(1) is assumed.

How do arrays and lists differ?

Arrays typically contain a static length. Lists typically have a dynamically changing size.

What is the sum of 1 + 2 + … n?

If n is even, you can sum two elelemtns in the summation to produce n+1, n/2 times. If n is odd, you can add 0 to the summation, and sum two elements in the summation to produce n, (n+1)/2 tomes. This gives a total of (n+1)*n/2 for both cases.

StringBuilder

A resizable array of strings. Can be converted into a string. Greatly reduces time complexity for string concatenation.