Quickly finding if there are 2 or more equal numbers

Question

I have an array of N different numbers that change frequently. After every change there is a chance that two or more numbers have become equal, and I don't want that. The number N can be as big as the maximum possible integer. Knowing that changes happen frequently, I don't want to compare each number with each one of the rest after each change.

How can I quickly find if there are at least 2 equal numbers in the array?

Answer 1

It really depends on what other constraints you have, e.g.:

1. Do you need to maintain the order in which the number come in?
2. Are the numbers are only ever added, or are they deleted too?
3. What is a more common operation: add/delete or check for dupes?
4. What do you need to keep - the set (i.e., unique numbers) or the multiset (numbers with their multiplicities)?

There are two basic options: a Binary Search Tree and a Hash Table.

The former will give you O(log(n)) operations on average, the latter - O(1); the actual results will depend on what kind of stream you have (are the numbers random? increasing? follow a weird non-obvious pattern?)

If you decide to go for BST, remember that you will have to keep it balanced.

Example (untested)

(defparameter *my-data-array* (make-array 100000))
;; fill *my-data-array*
(defparameter *my-data-table*
  (let ((ht (make-hash-table)))
    (loop for v across *my-data-array*
        do (incf (gethash v *my-data-table* 0)))
    ht))
(defun modify-data-array (pos new-value)
  (let* ((old-value (aref *my-data-array* pos))
         (old-count (decf (gethash old-value *my-data-table*)))
         (new-count (incf (gethash new-value *my-data-table* 0))))
    (setf (aref *my-data-array* pos) new-value)
    (case old-count
      (0 ; old-value is now not in the array
       ...)
      (1 ; old-value is now unique
       ...)
      (t ; old-value is still not unique
       ...))
     (case new-count
      (1 ; new-value was not in the array before
       ...)
      (2 ; new-value was unique before, but not anymore
       ...)
      (t ; new-value was not unique
       ...))))