Shazam算法采用傅里叶变换将时域信号转换为频域信号，并获得音频指纹，最后匹配指纹契合度来识别音频。

1、AudioSystem获取音频

奈奎斯特-香农采样定理告诉我们，为了能捕获人类能听到的声音频率，我们的采样速率必须是人类听觉范围的两倍。人类能听到的声音频率范围大约在20Hz到20000Hz之间，所以在录制音频的时候采样率大多是44100Hz。这是大多数标准MPEG-1 的采样率。44100这个值最初来源于索尼，因为它可以允许音频在修改过的视频设备上以25帧（PAL）或者30帧（ NTSC）每秒进行录制，而且也覆盖了专业录音设备的20000Hz带宽。所以当你在选择录音的频率时，选择44100Hz就好了。
定义音频格式：

    public static float sampleRate = 44100;
    public static int sampleSizeInBits = 16;
    public static int channels = 2; // double
    public static boolean signed = true; // Indicates whether the data is signed or unsigned
    public static boolean bigEndian = true; // Indicates whether the audio data is stored in big-endian or little-endian order
    public AudioFormat getFormat() {
        return new AudioFormat(sampleRate, sampleSizeInBits, channels, signed,
                bigEndian);
    }

调用麦克风获取音频，保存到out中

    public static ByteArrayOutputStream out = new ByteArrayOutputStream();1

        try {
            AudioFormat format = smartAuto.getFormat(); // Fill AudioFormat with the settings
            DataLine.Info info = new DataLine.Info(TargetDataLine.class, format);
            startTime = new Date().getTime();
            System.out.println(startTime);
            SmartAuto.line = (TargetDataLine) AudioSystem.getLine(info);
            SmartAuto.line.open(format);
            SmartAuto.line.start();
            new FileAnalysis().getDataToOut("");
            while (smartAuto.running) {
                checkTime(startTime);
            }
            SmartAuto.line.stop();
            SmartAuto.line.close();
        } catch (Throwable e) {
            e.printStackTrace();
        }

获取到的out数据需要通过傅里叶变换，从时域信号转换为频域信号。
傅里叶变换

public Complex[] fft(Complex[] x) {
        int n = x.length;

        // 因为exp(-2i*n*PI)=1，n=1时递归原点
        if (n == 1){
            return x;
        }

        // 如果信号数为奇数，使用dft计算
        if (n % 2 != 0) {
            return dft(x);
        }

        // 提取下标为偶数的原始信号值进行递归fft计算
        Complex[] even = new Complex[n / 2];
        for (int k = 0; k < n / 2; k++) {
            even[k] = x[2 * k];
        }
        Complex[] evenValue = fft(even);