There is an obvious lack of concurrency control with AlgorithmId.oidTable, which can get initialized by two different threads, with rare failures.

Here's a repro that fails for us about 1% of the time:

import java.util.*;
import java.util.concurrent.*;
import sun.security.x509.AlgorithmId;

public class AlgorithmIdBug {
    public static void main(String[] args) throws Throwable {
        final String[] algorithmNames = {
            "PBKDF2WITHHMACSHA1",
            "PBEWITHMD5ANDDES",
            "DSA",
            "SHA384WITHRSA",
            "RSA",
            "SHA1WITHDSA",
            "SHA512WITHRSA",
            "MD2WITHRSA",
            "PBEWITHSHA1ANDDESEDE",
            "SHA1WITHRSA",
            "DIFFIEHELLMAN",
            "MD5WITHRSA",
            "PBEWITHSHA1ANDRC2_40",
            "SHA256WITHRSA",
        };

        final int THREADS = 2;
        final ExecutorService pool = Executors.newFixedThreadPool(THREADS);
        final CountDownLatch startingGate = new CountDownLatch(THREADS);
        final Runnable r = new Runnable() { public void run() {
            startingGate.countDown();
            do {} while (startingGate.getCount() > 0);
            try {
                for (String algorithmName : algorithmNames)
                    AlgorithmId.get(algorithmName);
            } catch (Throwable fail) {
                throw new AssertionError(fail);
            }
        }};
        final ArrayList<Future<?>> futures = new ArrayList<>();
        for (int i = 0; i < THREADS; i++)
            futures.add(pool.submit(r));
        pool.shutdown();
        for (Future<?> future : futures) future.get();
    }
}

giving intermittent

Caused by: java.security.NoSuchAlgorithmException: unrecognized algorithm name: SHA512WITHRSA
at sun.security.x509.AlgorithmId.get(AlgorithmId.java:407)
at AlgorithmIdBug$1.run(AlgorithmIdBug.java:32)