Explicando por que recriar o array demora mais:
A JVM precisa procurar um bloco contínuo de memória para alocar o espaço, e caso não conseguir, ela vai ativar um full garbage colector e desfragmentar o espaço de memória, movendo os objetos em memória até ela liberar espaço. Se mesmo assim não conseguir, aí ela atira um OutOfMemoryError.
Um grande problema em fazer benchmarks em java é que a jvm efetua várias otimizações ao executar.
Transforme, por exemplo, a criação do array num método, a limpeza do array em outro, e rode ambos num for, mil vezes antes de comparar os tempos.
Verá que a criação do array se torna muito mais rápido.
Não sei como utilizar um BitSet nesse caso seria vantajoso, já que você precisa armazenar inteiros e não bits.
Uma outra boa forma que pode ser aliada ao uso de mapas de representação binária é a organização de arrays em blocos contíguos distribuindo o custo em tempo de inclusão e remoção, ou a aplicação da técnica de tratamento de matrizes esparsas.
Uma estrutura inteligente combina as várias técnicas estruturais conforme a utilização.
Estou começando agora o estudo de Inteligência Artificial, mas creio sua aplicação deve ser bem interessante para otimização de bibliotecas atuais.