1:
java.util.TreeSet<E>
сортированный java.util.Vector<E>
сортированный java.util.ArrayList<E>

2:
class Fib {
	private AtomicReference<BigInteger> t1;
	private AtomicReference<BigInteger> t2;

	public Fib() {
		t1 = new AtomicReference<BigInteger>(0)
		t2 = new AtomicReference<BigInteger>(1)
	}

	public BigInteger next() {
		return t2.accumulateAndGet(t1.getAndSet(t2.get), (BigInteger x, BigInteger y) -> x + y)
	}
}

3:
a) Использование массива в качестве ключа в Map: hashCode массива строится по его адресу в памяти, и поиск в Map по идентичному массиву (но другому) в качестве ключа не позволит получить элемент (для получения нужна ссылка на тот массив-ключ, элемент с которым был добавлен в Map)

4:
0x3f