public void Insert(Key key) {
		List<Node<Key>> prev = new ArrayList<Node<Key>>(kMaxHeight);
		for (int i = 0; i < kMaxHeight; i++) {
			prev.add(new Node<Key>(null, kMaxHeight));
		}
		Node<Key> x = FindGreaterOrEqual(key, prev);
		assert (x == null || compare_.compare(key, x.key) != 0);
		int height = RandomHeight();
		if (height > GetMaxHeight()) {
			for (int i = GetMaxHeight(); i < height; i++) {
				prev.set(i, head_);
			}
			// It is ok to mutate max_height_ without any synchronization
			// with concurrent readers. A concurrent reader that observes
			// the new value of max_height_ will see either the old value of
			// new level pointers from head_ (NULL), or a new value set in
			// the loop below. In the former case the reader will
			// immediately drop to the next level since NULL sorts after all
			// keys. In the latter case the reader will use the new node.
			max_height_.NoBarrier_Store(height);
		}

		x = new Node<Key>(key, height);
		for (int i = 0; i < height; i++) {
			// NoBarrier_SetNext() suffices since we will add a barrier when
			// we publish a pointer to "x" in prev[i].
			x.NoBarrier_SetNext(i, prev.get(i).NoBarrier_Next(i));
			prev.get(i).SetNext(i, x);
		}

	}